一本通 1.1 例 5【智力大冲浪】

首先根据贪心，容易得出应该尽可能的不失去扣钱数多的游戏，因此先按照扣钱数进行排序。随后从后往前枚举时间，能完成就完成，因为有可能出现扣钱数多的游戏但时间宽裕、扣钱数相对少但时间紧的情况，因为答案要求最大，所以尽量每个游戏的时间都向后安排，因为前面的时间是所有游戏都最可能用的，而后面的时间一定没有前面的时间更优。$O(n$²$)$

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 using namespace std;
 4 int n, m, choose[510];
 5 struct Str {int t, c;}stu[510];
 6 int cmp(Str a, Str b) {return a.c > b.c;}
 7 int main()
 8 {
 9     scanf("%d %d", &m, &n); for(int i = 1; i <= n; ++i) scanf("%d", &stu[i].t); for(int i = 1; i <= n; ++i) scanf("%d", &stu[i].c);
10     sort(stu + 1, stu + n + 1, cmp);
11      for(int i = 1; i <= n; ++i)
12     {
13         int time = stu[i].t;
14         while(choose[time]) --time;
15         if(time == 0) m -= stu[i].c; 
16         else choose[time] = 1;
17     }
18     printf("%d", m);
19     return 0;
20 }