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

郭大侠与Rabi-Ribi

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

title

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

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

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

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

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

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

Input

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

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

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

$1 \leq N \leq 100000$

$1 \leq a [i] \leq 5000$

$1 \leq v [i] \leq 1000$

Output

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

Sample input and output

Sample Input	Sample 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[100010];
int cmp(is x,is y)
{
    if(x.v!=y.v)
    return x.v>y.v;
    return x.w>y.w;
}
int flag[101000];
int check(int x)
{
    for(int i=x;i>0;i--)
    if(!flag[i])
    return i;
    return -1;
}
int main()
{
    int x,y,z,i,t;
    while(~scanf("%d",&x))
    {
        memset(flag,0,sizeof(flag));
        for(i=0;i<x;i++)
        scanf("%d",&a[i].w);
        for(i=0;i<x;i++)
        scanf("%d",&a[i].v);
        sort(a,a+x,cmp);
        int kui=0;
        for(i=0;i<x;i++)
        {
            int gg=check(a[i].w);
            if(gg!=-1)
            {
                flag[gg]=1;
                kui+=a[i].v;
            }
        }
        printf("%d
",kui);
    }
    return 0;
}

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

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

优先队列：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define esp 0.00000000001
const int N=2e5+10,M=1e6+10,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=1;i<=x;i++)
        scanf("%d",&a[i].x);
        for(t=1;t<=x;t++)
        scanf("%d",&a[t].y);
        sort(a+1,a+x+1,cmp);
        priority_queue<int>q;
        int flag=1,ans=0;
        for(i=5000;i>=1;i--)
        {
            while(a[flag].x>=i)
            q.push(a[flag].y),flag++;
            if(!q.empty())
            ans+=q.top(),q.pop();
        }
        printf("%d
",ans);
    }
    return 0;
}