郭大侠与Rabi-Ribi（优先队列）

2023-09-05 阅读 43 评论 0

摘要：郭大侠与Rabi-Ribi Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others) Submit Status 最近郭大侠迷上了玩Rabi-Ribi这个游戏。 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≤N≤100000

1≤a[i]≤5000

1≤v[i]≤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

Source

2016 UESTC Training for Data Structures

思路：

这题其实就是贪心，首先我要选时间小的放进队列，因为时间大的有更多机会进入队列。然后如果存在有比队列的数大的，而且小于最大时间的，

就将队列的数更换为大的。

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<queue>
#include<functional>
using namespace std;
#define lson (rt<<1)
#define rson (rt<<1|1)
#define T 100000 + 50
#define inf 0x3f3f3f3f
typedef long long ll;pair<int,int> pir[T];
priority_queue< int,vector<int>,greater<int> > q;int main()
{
#ifdef zscfreopen("input.txt","r",stdin);
#endifint n,m,i,j,k;while(~scanf("%d",&n)){for(i=0;i<n;++i)scanf("%d",&pir[i].first);for(i=0;i<n;++i)scanf("%d",&pir[i].second);sort(pir,pir+n);for(i=0;i<n;++i){if(q.size()<pir[i].first)q.push(pir[i].second);//将时间小的放进去else if(q.top()<pir[i].second)q.pop(),q.push(pir[i].second);//如果选到的数比现在的数小，更新}int ans = 0;while(!q.empty()){ans += q.top();q.pop();}printf("%d\n",ans);}return 0;
}

原文链接：https://808629.com/1184.html

上一篇：cdoj1338郭大侠与英雄学院

下一篇：2016 UESTC Training for Data Structures J - 郭大侠与Rabi-Ribi CDOJ 1334 优先队列