洛谷P1230智力大冲浪 题解
题目描述
小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴！因为这些钱还不一定都是你的？！接下来主持人宣布了比赛规则：
首先，比赛时间分为n个时段(\(n≤500\))，它又给出了很多小游戏，每个小游戏都必须在规定期限ti前完成(\(1≤t_i≤n\))。如果一个游戏没能在规定期限前完成，则要从奖励费\(m\)元中扣去一部分钱\(w_i\)，\(w_i\)为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！注意：比赛绝对不会让参赛者赔钱!
输入格式
输入文件riddle.in，共\(4\)行。
第1行为\(m\)，表示一开始奖励给每位参赛者的钱；
第2行为\(n\)，表示有\(n\)个小游戏；
第3行有\(n\)个数，分别表示游戏\(1\)到\(n\)的规定完成期限；
第4行有\(n\)个数，分别表示游戏\(1\)到\(n\)不能在规定期限前完成的扣款数。
输出格式
输出文件riddle.out，仅1行。表示小伟能赢取最多的钱。
输入输出样例
输入 #1
10000
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
输出 #1
9950
解析
堆+贪心
我们有一个总数，目的是减去一部分数而使得总数减去这一部分数后总数为最大的。
首先将所有的价值取相反数加到一个变量里，然后我们就把求最小值转换为求最大值了。
根据时间期限按照从小到大进行排序，然后按照以下思路：
- 如果当前时间小于等于当前期限，那么就说明该任务是可以做的，把做完该任务的价值放入堆中；
- 反之大于当前期限，我们就比较堆顶价值与当前价值的大小，如果堆顶价值小于当前价值，那就进行替换。
将堆中的元素全部相加然后与总数相加就是答案。
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <iomanip>
#include <cstring>
#define re register
#define Max 550
struct IQ {
int x, val;
friend bool operator < (IQ a, IQ b) {
return a.x < b.x;
}
}t[Max];
int n, ans, m, T = 1;
std :: priority_queue<int, std :: vector<int>, std :: greater<int> > q;
int main() {
scanf("%d%d",&m,&n);
for(re int i = 1; i <= n; ++ i) scanf("%d",&t[i].x);
for(re int i = 1; i <= n; ++ i) scanf("%d",&t[i].val), ans += -t[i].val;
std :: sort(t+1,t+1+n);
for(re int i = 1; i <= n; ++ i) {
if(T <= t[i].x) T ++, q.push(t[i].val);
else if(t[i].val > q.top()) q.pop(), q.push(t[i].val);
}
while(!q.empty()) ans += q.top(), q.pop();
printf("%d",m+ans);
return 0;
}
