郭大侠与Rabi-Ribi

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
Submit Status

cdoj 1334  郭大侠与Rabi-Ribi  贪心+数据结构-LMLPHP

最近郭大侠迷上了玩Rabi-Ribi这个游戏。

Rabi-Ribi呢,是一个打兔子的动作冒险游戏,萌萌哒的兔子在地上跑来跑去,好萌好萌呀~

这个游戏是这样玩的,郭大侠作为一个主角,拿着一个小锤子,他的目标是敲晕兔子,然后最后把这些敲晕的兔子都带回家。

当然咯,郭大侠想带回的兔子的总价值最高~

但是,兔子实在是太多了,郭大侠的锤子每一秒钟只能敲晕一只兔子,而且每一只兔子只会在地面上逗留a[i]a[i]秒,在a[i]a[i]秒之后,这一只兔子就会跑回自己的小窝里面。

所以郭大侠面临一些抉择,希望你能帮助他。

Input

第一行包含一个整数NN表示有NN个兔子在地上跑来跑去。

第二行NN个用空格分隔的整数a[i]a[i]表示第i只兔子冒出后停留的时间

第三行NN个用空格分隔的整数v[i]v[i]表示第i只兔子的价值。

1≤N≤1000001≤N≤100000

1≤a[i]≤50001≤a[i]≤5000

1≤v[i]≤10001≤v[i]≤1000

Output

输出郭大侠最多能获得的价值是多少

Sample input and output

5
5 3 6 1 4
7 9 2 1 5
24
3
1 1 1
1 2 3
3

Hint

死宅真可怕,连可爱的兔子都要敲晕带回家 QAQ

思路:这题的数据水;在某个时间点,放入能放的最大值;倒着写;    

   下面是三种不一样的解法;

暴力:纯暴力,因为数据水所以过了;

#include<bits/stdc++.h>
using namespace std;
#define ll __int64
#define inf 0xfffffff
struct is
{
int w,v;
}a[];
int cmp(is x,is y)
{
if(x.v!=y.v)
return x.v>y.v;
return x.w>y.w;
}
int flag[];
int check(int x)
{
for(int i=x;i>;i--)
if(!flag[i])
return i;
return -;
}
int main()
{
int x,y,z,i,t;
while(~scanf("%d",&x))
{
memset(flag,,sizeof(flag));
for(i=;i<x;i++)
scanf("%d",&a[i].w);
for(i=;i<x;i++)
scanf("%d",&a[i].v);
sort(a,a+x,cmp);
int kui=;
for(i=;i<x;i++)
{
int gg=check(a[i].w);
if(gg!=-)
{
flag[gg]=;
kui+=a[i].v;
}
}
printf("%d\n",kui);
}
return ;
}

线段树:线段树维护+二分查找

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define esp 0.00000000001
const int N=2e5+,M=1e6+,inf=1e9;
struct is
{
int x,y;
}a[N];
int ans[N];
int cmp(is x,is y)
{
if(x.y!=y.y)
return x.y>y.y;
return x.x>y.x;
}
int minn[N];
void update(int p,int c,int l,int r,int pos)
{
if(p==l&&p==r)
{
minn[pos]=c;
return;
}
int mid=(l+r)>>;
if(p<=mid)
update(p,c,l,mid,pos<<);
if(p>mid)
update(p,c,mid+,r,pos<<|);
minn[pos]=min(minn[pos<<],minn[pos<<|]);
}
int query(int L,int R,int l,int r,int pos)
{
if(L<=l&&R>=r)
return minn[pos];
int mid=(l+r)>>;
int ans=inf;
if(L<=mid)
ans=min(ans,query(L,R,l,mid,pos<<));
if(R>mid)
ans=min(ans,query(L,R,mid+,r,pos<<|));
return ans;
}
int getpos(int x)
{
int st=;
int en=x;
if(query(st,en,,,)!=)
return -;
while(st<en)
{
int mid=(st+en)>>;
if(query(mid+,en,,,)!=)
en=mid;
else
st=mid+;
}
if(query(st,st,,,)==)
return st;
if(query(st+,st+,,,)==)
return st+;
}
int main()
{
int x,y,z,i,t;
while(~scanf("%d",&x))
{
memset(ans,,sizeof(ans));
memset(minn,,sizeof(minn));
for(i=;i<=x;i++)
scanf("%d",&a[i].x);
for(t=;t<=x;t++)
scanf("%d",&a[t].y);
sort(a+,a+x+,cmp);
for(i=;i<=x;i++)
{
int pos=getpos(a[i].x);
if(pos>&&ans[pos]==)
{
update(pos,a[i].y,,,);
ans[pos]=a[i].y;
}
}
int sum=;
for(i=;i<=;i++)
sum+=ans[i];
printf("%d\n",sum);
}
return ;
}

优先队列:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define esp 0.00000000001
const int N=2e5+,M=1e6+,inf=1e9;
struct is
{
int x,y;
}a[N];
int ans[N];
int cmp(is x,is y)
{
return x.x>y.x;
}
int main ()
{
int x,y,z,i,t;
while(~scanf("%d",&x))
{
for(i=;i<=x;i++)
scanf("%d",&a[i].x);
for(t=;t<=x;t++)
scanf("%d",&a[t].y);
sort(a+,a+x+,cmp);
priority_queue<int>q;
int flag=,ans=;
for(i=;i>=;i--)
{
while(a[flag].x>=i)
q.push(a[flag].y),flag++;
if(!q.empty())
ans+=q.top(),q.pop();
}
printf("%d\n",ans);
}
return ;
}

郭大侠与Rabi-Ribi

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
Submit Status

cdoj 1334  郭大侠与Rabi-Ribi  贪心+数据结构-LMLPHP

最近郭大侠迷上了玩Rabi-Ribi这个游戏。

Rabi-Ribi呢,是一个打兔子的动作冒险游戏,萌萌哒的兔子在地上跑来跑去,好萌好萌呀~

这个游戏是这样玩的,郭大侠作为一个主角,拿着一个小锤子,他的目标是敲晕兔子,然后最后把这些敲晕的兔子都带回家。

当然咯,郭大侠想带回的兔子的总价值最高~

但是,兔子实在是太多了,郭大侠的锤子每一秒钟只能敲晕一只兔子,而且每一只兔子只会在地面上逗留a[i]a[i]秒,在a[i]a[i]秒之后,这一只兔子就会跑回自己的小窝里面。

所以郭大侠面临一些抉择,希望你能帮助他。

Input

第一行包含一个整数NN表示有NN个兔子在地上跑来跑去。

第二行NN个用空格分隔的整数a[i]a[i]表示第i只兔子冒出后停留的时间

第三行NN个用空格分隔的整数v[i]v[i]表示第i只兔子的价值。

1≤N≤1000001≤N≤100000

1≤a[i]≤50001≤a[i]≤5000

1≤v[i]≤10001≤v[i]≤1000

Output

输出郭大侠最多能获得的价值是多少

Sample input and output

5
5 3 6 1 4
7 9 2 1 5
24
3
1 1 1
1 2 3
3

Hint

死宅真可怕,连可爱的兔子都要敲晕带回家 QAQ

05-11 13:37