郭大侠与Rabi-Ribi

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

技术分享

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

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

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

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

但是，兔子实在是太多了，郭大侠的锤子每一秒钟只能敲晕一只兔子，而且每一只兔子只会在地面上逗留 $a [i]$

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

Input

第一行包含一个整数 $N$

第二行 $N$

第三行 $N$

$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
55 3 6 1 47 9 2 1 5	24
31 1 11 2 3	3

Hint

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

代码

 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<vector> 5 #include<queue> 6 #include<algorithm> 7 using namespace std; 8  9 struct node{10     int t,w;11 }e[100005];12 13 struct cmp1{14     bool operator ()(node a,node b){15         return a.w<b.w;//最大值优先 16     }17 };18 19 bool cmp2(node a,node b){20     return a.t>b.t;//最大值优先 21 }22 23 priority_queue<node,vector<node>,cmp1> q;24 int n,ans,point;25 26 int main(){27 //    freopen("01.in","r",stdin);28     scanf("%d",&n);29     for(int i=1;i<=n;i++) scanf("%d",&e[i].t);30     for(int i=1;i<=n;i++) scanf("%d",&e[i].w);31     sort(e+1,e+n+1,cmp2);32     33     34     int i=5000;point=1;35     while(i>0){36         while(e[point].t>=i){37             q.push(e[point++]);38         }39         if(!q.empty()) ans+=q.top().w,q.pop();40         i--;41     }42     43     printf("%d\n",ans);44     return 0;45 }

就是靠优先队列，倒着来有最优结果，在某个时刻不着急砸兔子

先把兔子加到队列里面来，相当于获取砸这一只的机会

当要砸的时候，获取队列里最贵的一只就好

貌似有一道经典题目一样，大意就是开车绕个圈加油，问最少加几次油，也可以看成类似经过加油站获取加油的机会，、油不够的时候，获取最大值

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

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > cdoj 1334 郭大侠与Rabi-Ribi Label:贪心+数据结构