https://www.51nod.com/Challenge/Problem.html#!#problemId=2070
小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴！因为这些钱还不一定都是你的？！接下来主持人宣布了比赛规则：
首先，比赛时间分为n个时段(n≤500)，它又给出了很多小游戏，每个小游戏都必须在规定期限ti前完成(1≤ti≤n)。如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣去一部分钱wi，wi为自然数，不同的游戏扣去的钱是不一样的。现在你要设计方法，使得你能得到最多的奖励。
输入
输入共 4 行
第 1 行为 m ，表示一开始奖励给每位参赛者的钱；
第 2 行为 n，表示有 n 个小游戏；
第 3 行有 n 个数，分别表示游戏 1 到 n 的规定完成期限；
第 4 行有 n 个数，分别表示游戏 1 到 n 不能在规定期限前完成的扣款数。
输出
输出文件仅 1 行。表示小伟能赢取最多的钱。
输入样例
10000
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
输出样例
9950
方法一：按截止时间排序
考虑两个游戏，如果完成时间都在规定期限之前，顺序是无所谓的。如果新加的游戏使得完成时间大于规定期限那么选择一个 wi 小的删去，可能是删掉新加入的游戏也可能是已加入的
方法二：按收益排序
对于两个游戏，首先尝试收益高的(截止时间 = t )，是否能安排上。如果 （ t-1 , t ）时间段可以用则安排上并标记，否则尝试 （t-2 , t-1）时间段，依序往下，如都已被占用 ，则放弃该活动。 不能安排的活动不能替代已安排的活动。
过程中用并查集管理时间段。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <bits/stdc++.h>
using namespace std;
#define MAX 500+10
pair<int ,int > a[MAX];
priority_queue<int> p;
int n,m,ans;
int main(){
freopen("in","r",stdin);
scanf("%d\n%d",&m,&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i].first);
for(int i=0;i<n;i++)
scanf("%d",&a[i].second);
sort(a,a+n);
for(int i=0;i<n;i++){
p.push(-a[i].second);
if(p.size()>a[i].first){
ans+=p.top();
p.pop();
}
}
printf("%d",m+ans);
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <bits/stdc++.h>
using namespace std;
const int MAX=500+10;
pair<int ,int > a[MAX];
int f[MAX],m,n,ans,t=0;
int find(int x){
return x==f[x]? x :f[x] = find(f[x]);
}
int cmp (const pair<int ,int > &x, const pair<int ,int >&y){
return x.second>y.second;
}
int main(){
freopen("in","r",stdin);
scanf("%d%d",&m,&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i].first);
if(a[i].first > n) f[a[i].first] =n;
}
for(int i=0;i<n;i++)
scanf("%d",&a[i].second);
for(int i=0;i<=n;i++)
f[i]=i;
sort(a,a+n,cmp);
for(int i=0;i<n;i++){
int t= find(a[i].first);
if(t>0) f[t] = f[t-1];
else ans+=a[i].second;
}
printf("%d",m-ans);
return 0;
}
|