ZCMU 5015

Description

zbj最近开始玩一款单机类游戏，这个游戏很有意思，所有任务的接受是没有限制的，所以他一次性把所有可以接的任务都接下了，但是这时候他发现了一个很严肃的问题，他总共接受了 n 个任务，每个任务有剩余完成时间和这个任务的金钱奖励

现在为了方便，zbj假设现在时间为 0，他知道了每个任务的剩余完成时间和完成金钱，并且完成一个任务的时间都是1。

希望你可以告诉他该怎么完成任务才能尽量获得更多的钱

Input

第一行包含一个整数 n，表示共有 n 个任务。 第二行包含 n 个整数 ai，表示第 i 项任务的剩余完成时间 第三行包含 n 个整数 bi，表示第 i 项任务的金钱奖励 (1<=ai,bi,n<=1000)

Output

输出包含一个整数，表示蒜头君最多可以获得的金钱。

Sample Input

3 1 3 1 6 2 3

Sample Output

8

HINT

HINT:三个任务的剩余时间分别为1 3 1，对应的金钱奖励为6 2 3，所以完成1号任务和2号任务，3号任务无法完成，即最多可以获得金钱为8.

题解： 因为任务完成需要1分钟所以每个时间节点最多完成一个，把奖金从大到小排序，若干奖金相同，把时间从小到大排序。然后遍历一遍，由于时间1和3之间空了一个2所以二号任务应该完成时间在2.这也是我开始没理解到的地方 code：

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; struct R { int money; int time; } x[1005]; bool cmp(R a,R b) { if(a.money!=b.money) return a.money>b.money; else return a.time<b.time; } int main() { int n; scanf("%d",&n); for(int i=0; i<n; i++) scanf("%d",&x[i].time); for(int i=0; i<n; i++) scanf("%d",&x[i].money); sort(x,x+n,cmp); //for(int i=0;i<n;i++)printf("%d %d\n",x[i].money,x[i].time); int m[1005]= {0}; int sum=0; int j=0; for(int i=0; i<n; i++) { j=x[i].time; while(m[j]==1&&j!=0) j--; if(j>0) { m[j]=1; sum+=x[i].money; } } printf("%d\n",sum); }