企业官网建设流程全解析

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

输入 #1

10000 7 4 2 4 3 1 4 6 70 60 50 40 30 20 10

输出 #1

9950

说明/提示

对于100 % 100\%100%的数据，1 ≤ n ≤ 500 1 \le n \le 5001≤n≤500，1 ≤ m ≤ 5 × 10 5 1 \le m \le 5 \times 10^51≤m≤5×105，1 ≤ t i ≤ n 1 \le t_i \le n1≤ti​≤n，1 ≤ w i ≤ 1000 1 \le w_i \le 10001≤wi​≤1000。

解题思路

本题核心是贪心算法+空闲时段分配，属于经典的任务调度最优解问题。题目要求最大化剩余奖金，等价于最小化扣款总额，因此采用贪心策略：优先完成扣款金额更高的游戏。将所有游戏按扣款数值降序排序，依次为每个游戏分配时间：从其规定期限开始，向前查找第一个未被占用的时段；若找到则占用该时段完成游戏，若未找到则无法完成，累加对应扣款。最终用初始奖金减去总扣款，即为最大可获得的奖金。算法时间复杂度为O ( n 2 ) O(n^2)O(n2)，完美适配n ≤ 500 n≤500n≤500的数据范围，实现简单且结果最优。

总结

核心逻辑：贪心优先处理扣款最多的游戏，为其分配最晚的可用时段，最小化总扣款。
关键操作：按扣款降序排序、逆序查找空闲时段、统计无法完成的扣款总和。
效率保障：暴力查找空位适配小数据规模，逻辑直观，计算高效。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;structben{ll t,val;}a[505];ll vis[505];intcmp(constben&x,constben&y){returnx.val>y.val;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll m,n;scanf("%lld%lld",&m,&n);for(ll i=1;i<=n;i++){scanf("%lld",&a[i].t);}for(ll i=1;i<=n;i++){scanf("%lld",&a[i].val);}sort(a+1,a+n+1,cmp);ll ans=0;for(ll i=1;i<=n;i++){ll tag=0;for(ll j=a[i].t;j;j--){if(vis[j]==0){vis[j]=1;tag=1;break;}}if(tag==0){for(ll j=n;j;j--){if(vis[j]==0){vis[j]=1;break;}}ans+=a[i].val;}}printf("%lld\n",m-ans);return0;}