首页 > 代码库 > 郭大侠与Rabi-Ribi (优先队列)
郭大侠与Rabi-Ribi (优先队列)
最近郭大侠迷上了玩Rabi-Ribi这个游戏。
Rabi-Ribi呢，是一个打兔子的动作冒险游戏，萌萌哒的兔子在地上跑来跑去，好萌好萌呀~
这个游戏是这样玩的，郭大侠作为一个主角，拿着一个小锤子，他的目标是敲晕兔子，然后最后把这些敲晕的兔子都带回家。
当然咯，郭大侠想带回的兔子的总价值最高~
但是，兔子实在是太多了，郭大侠的锤子每一秒钟只能敲晕一只兔子，而且每一只兔子只会在地面上逗留a[i]秒，在a[i]秒之后，这一只兔子就会跑回自己的小窝里面。
所以郭大侠面临一些抉择，希望你能帮助他。
Input
第一行包含一个整数N表示有N个兔子在地上跑来跑去。
第二行NN个用空格分隔的整数a[i]表示第i只兔子冒出后停留的时间
第三行NN个用空格分隔的整数v[i]表示第i只兔子的价值。
1≤N≤100000
1≤a[i]≤5000
1≤v[i]≤1000
Output
输出郭大侠最多能获得的价值是多少
Sample Input
55 3 6 1 47 9 2 1 531 1 11 2 3Sample Output
243Hint
死宅真可怕，连可爱的兔子都要敲晕带回家 QAQ
//一眼看去貌似十分简单，随手写了已发wa了才，重新认识到这题！
因为每秒可以敲一只兔子，所以，将兔子按时间排序，然后，要使每秒可以创造的价值足够大，所以，就是选t只最大价值的兔子即可
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <queue> 5 #include <algorithm> 6 using namespace std; 7 #define LL long long 8 #define MX 100005 9 struct Tu10 {11 int t,v;12 bool operator < (const Tu& b)const13 {14 return t<b.t;15 }16 }tu[MX];17 18 int main()19 {20 int n;21 scanf("%d",&n);22 for (int i=0;i<n;i++)23 scanf("%d",&tu[i].t);24 for (int i=0;i<n;i++)25 scanf("%d",&tu[i].v);26 sort(tu,tu+n);27 priority_queue<int ,vector<int>,greater<int> > Q;28 for (int i=0;i<n;i++)29 {30 if (tu[i].t>Q.size())31 {32 Q.push(tu[i].v);33 }34 else35 {36 Q.push(tu[i].v);37 Q.pop();38 }39 }40 int ans = 0;41 while (!Q.empty()) ans+=Q.top(),Q.pop();42 printf("%d\n",ans);43 return 0;44 }
郭大侠与Rabi-Ribi (优先队列)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。