P1230 智力大冲浪网页链接P1230 智力大冲浪题目描述小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者主持人为了表彰大家的勇气先奖励每个参赛者m mm元。先不要太高兴因为这些钱还不一定都是你的。接下来主持人宣布了比赛规则首先比赛时间分为n nn个时段它又给出了很多小游戏每个小游戏都必须在规定期限t i t_iti​前完成。如果一个游戏没能在规定期限前完成则要从奖励费m mm元中扣去一部分钱w i w_iwi​w i w_iwi​为自然数不同的游戏扣去的钱是不一样的。当然每个游戏本身都很简单保证每个参赛者都能在一个时段内完成而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者小伟很想赢得冠军当然更想赢取最多的钱注意比赛绝对不会让参赛者赔钱!输入格式第一行为m mm表示一开始奖励给每位参赛者的钱第二行为n nn表示有n nn个小游戏第三行有n nn个数分别表示游戏1 11到n nn的规定完成期限第四行有n nn个数分别表示游戏1 11到n nn不能在规定期限前完成的扣款数。输出格式输出仅一行表示小伟能赢取最多的钱。输入输出样例 #1输入 #110000 7 4 2 4 3 1 4 6 70 60 50 40 30 20 10输出 #19950说明/提示对于100 % 100\%100%的数据1 ≤ n ≤ 500 1 \le n \le 5001≤n≤5001 ≤ m ≤ 5 × 10 5 1 \le m \le 5 \times 10^51≤m≤5×1051 ≤ t i ≤ n 1 \le t_i \le n1≤ti​≤n1 ≤ w i ≤ 1000 1 \le w_i \le 10001≤wi​≤1000。解题思路本题核心是贪心算法空闲时段分配属于经典的任务调度最优解问题。题目要求最大化剩余奖金等价于最小化扣款总额因此采用贪心策略优先完成扣款金额更高的游戏。将所有游戏按扣款数值降序排序依次为每个游戏分配时间从其规定期限开始向前查找第一个未被占用的时段若找到则占用该时段完成游戏若未找到则无法完成累加对应扣款。最终用初始奖金减去总扣款即为最大可获得的奖金。算法时间复杂度为O ( n 2 ) O(n^2)O(n2)完美适配n ≤ 500 n≤500n≤500的数据范围实现简单且结果最优。总结核心逻辑贪心优先处理扣款最多的游戏为其分配最晚的可用时段最小化总扣款。关键操作按扣款降序排序、逆序查找空闲时段、统计无法完成的扣款总和。效率保障暴力查找空位适配小数据规模逻辑直观计算高效。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;structben{ll t,val;}a[505];ll vis[505];intcmp(constbenx,constbeny){returnx.valy.val;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll m,n;scanf(%lld%lld,m,n);for(ll i1;in;i){scanf(%lld,a[i].t);}for(ll i1;in;i){scanf(%lld,a[i].val);}sort(a1,an1,cmp);ll ans0;for(ll i1;in;i){ll tag0;for(ll ja[i].t;j;j--){if(vis[j]0){vis[j]1;tag1;break;}}if(tag0){for(ll jn;j;j--){if(vis[j]0){vis[j]1;break;}}ansa[i].val;}}printf(%lld\n,m-ans);return0;}