【题目描述】
小明参加了一个巧夺大奖的游戏节目。主持人宣布了游戏规则：
1、游戏分为n 个时间段，参加者每个时间段可以选择一个小游戏。
2、游戏中共有n 个小游戏可供选择。
3、每个小游戏有规定的时限和奖励。对于第i 个小游戏，参加者必须在第Ti 个时间段结束前完成才能得到奖励Ri 。
小明发现，这些小游戏都很简单，不管选择哪个小游戏，他都能在一个时间段内完成。关键问题在于，如何安排每
个时间段分别选择哪个小游戏，才能使得总奖励最高？
【输入】
输入第一行，包含一个正整数n 。 n既是游戏时间段的个数，也是小游戏的个数。约定1≤n≤500 。
输入第二行，包含n 个正整数。第i 个正整数为 Ti，即第i 个小游戏的完成期限。约定1≤Ti≤n 。
输入第三行，包含n 个正整数。第i 个正整数为 Ri，即第i 个小游戏的完成奖励。约定1≤Ri≤1000 。
【输出】
输出一行，包含一个正整数C ，为最高可获得的奖励。
【输入样例】
7 4 2 4 3 1 4 6 70 60 50 40 30 20 10【输出样例】
230【提示】
样例解释1
7个时间段可分别安排完成第4、2、3、1、6、7、5个小游戏，其中第4、2、3、1、7个小游戏在期限内完成。因此，可以获得总计40+60+50+70+10=230 的奖励
解析：
测试数据
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
按完成时间排序
1 2 3 4 4 4 6
30 60 40 70 50 20 10
倒着选择游戏
6 可选为10
剩余：
1 2 3 4 4 4 6
30 60 40 70 50 20 -
5 因为可以拖延到5完成的游戏 只有6对应的10，10已被选择，所以5无可选游戏
剩余：
1 2 3 4 4 4 6
30 60 40 70 50 20 -
4 可选为70 50 20，选最大值70
剩余：
1 2 3 4 4 4 6
30 60 40 - 50 20 -
3 可选为4-50 4-20 3-40，选最大值50
剩余：
1 2 3 4 4 4 6
30 60 40 - - 20 -
2 可选为4-20 3-40 2-60，选最大值60
剩余：
1 2 3 4 4 4 6
30 - 40 - - 20 -
1 可选为4-20 3-40 1-30，选最大值40
剩余：
1 2 3 4 4 4 6
30 - - - - 20 -
最终数据：
6 5 4 3 2 1
10 0 70 50 60 40
40+60+50+70+10=230
#include <bits/stdc++.h> using namespace std; /* run this program using the console pauser or add your own getch, system("pause") or input loop */ int n; struct x{ int t,r; }; x a[500]; bool cmp(x a,x b){ if(a.t==b.t){ return a.r>b.r; } else return a.t>b.t; } int main(int argc, char** argv) { scanf("%d",&n); for(int i=0;i<n;i++)scanf("%d",&a[i].t); for(int i=0;i<n;i++)scanf("%d",&a[i].r); sort(a,a+n,cmp); /*for(int i=0;i<n;i++){ printf("%d-%d ",a[i].t,a[i].r); } cout<<endl;*/ long long sum=0; x *p_max; for(int i=a[0].t;i>0;i--){ p_max=NULL; for(int j=0;j<n;j++){ if(a[j].t>=i){ if(a[j].r>0){ if(p_max==NULL)p_max=&a[j]; else if(a[j].r>p_max->r)p_max=&a[j]; } } else break; } if(p_max!=NULL){ sum+=p_max->r; //cout<<p_max->r<<" "; p_max->r=0; } } cout<<sum; /*测试数据 7 4 2 4 3 1 4 6 70 60 50 40 30 20 10 按完成时间排序 1 2 3 4 4 4 6 30 60 40 70 50 20 10 倒着选择游戏 6 可选为10 剩余： 1 2 3 4 4 4 6 30 60 40 70 50 20 - 5 因为可以拖延到5完成的游戏 只有6对应的10，10已被选择，所以5无可选游戏 剩余： 1 2 3 4 4 4 6 30 60 40 70 50 20 - 4 可选为70 50 20，选最大值70 剩余： 1 2 3 4 4 4 6 30 60 40 - 50 20 - 3 可选为4-50 4-20 3-40，选最大值50 剩余： 1 2 3 4 4 4 6 30 60 40 - - 20 - 2 可选为4-20 3-40 2-60，选最大值60 剩余： 1 2 3 4 4 4 6 30 - 40 - - 20 - 1 可选为4-20 3-40 1-30，选最大值40 剩余： 1 2 3 4 4 4 6 30 - - - - 20 - 最终数据： 6 5 4 3 2 1 10 0 70 50 60 40 40+60+50+70+10=230 */ return 0; }
