郭大侠与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 ;

}