题目描述
输入格式
第一行一个整数n ,表示作业的数量;
接下来 n行,每行包括两个整数,第一个整数表示作业的完成期限,第二个数表示该作业的学分。
输出格式
输出一个整数表示可以获得的最大学分。保证答案不超过 C/C++ 的 int 范围
输入输出样例
输入 #1
7
1 6
1 7
3 2
3 1
2 4
2 5
6 1
输出 #1
15
说明/提示
思路一(有漏洞)
以第一关键字学分、第二关键字时间对 n 个作业进行排序。
从头开始遍历 n 个元素,用 now 记录当前时间,如果 now<hw[i].time 则 now++。
漏洞:可能学分 10、时间 9 的在前面,但学分 9、时间 1 的在后面,正解应该先拿学分 9,再拿学分 10。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
ll time, xf;
}hw[1000010];
bool cmp(node a, node b){
if(a.xf==b.xf)
return a.time<b.time;
return a.xf>b.xf;
}
int main(){
ll n;
// freopen("1.in", "r", stdin);
scanf("%lld", &n);
for(ll i=0; i<n; i++)
scanf("%lld%lld", &hw[i].time, &hw[i].xf);
sort(hw, hw+n, cmp);
ll now=0, sum=0;
for(int i=0; i<n; i++)
if(hw[i].time>now){
sum += hw[i].xf;
now++;
}
printf("%lld", sum);
return 0;
}
思路二(有漏洞)
以第一关键字时间、第二关键字时间对 n 个作业进行排序。
从头开始遍历 n 个元素,用 now 记录当前时间,如果 now<hw[i].time 则 now++。
漏洞:如果时间长所的学分更高,那么时间短但学分低的会浪费时间。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
ll time, fx;
}hw[1000010];
bool cmp(node a, node b){
if(a.time==b.time){
return a.fx>b.fx;
}
return a.time<b.time;
}
int main(){
ll n;
scanf("%lld", &n);
for(ll i=0; i<n; i++)
scanf("%lld%lld", &hw[i].time, &hw[i].fx);
sort(hw, hw+n, cmp);
ll now=0, sum=0;
//如果时间长所的学分更高,那么时间短但学分低的会浪费时间
for(int i=0; i<n; i++)
if(hw[i].time>now){
sum += hw[i].fx;
now++;
}
printf("%lld", sum);
return 0;
}
思路三(正解)
以第一关键字学分、第二关键字时间对 n 个作业进行排序。
并查集巧妙运用在时间轴上,将每个时间点都联系在一起,使每个时间点上得到的都是最优解。
#include<bits/stdc++.h>
using namespace std;
int bj[700010], flag;
struct node{
int time, xf;
}hw[1000010];
bool cmp(node a, node b){
if(a.xf==b.xf)
a.time<b.time;
return a.xf>b.xf;
}
int check(int x){
if(x==0) //找不着
return 0;
if(bj[x]==x){ //找着了
flag=1;
bj[x] = x-1;
return bj[x];
}
//没找着,但有找的空间
//寻找前面空闲时间并压缩路径
return bj[x] = check(bj[x]);
}
int main(){
int n;
for(int i=0; i<700010; i++)
bj[i]=i;
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d%d", &hw[i].time, &hw[i].xf);
sort(hw, hw+n, cmp);
int ans=0;
for(int i=0; i<n; i++){
flag=0;
bj[hw[i].time] = check(hw[i].time);
if(flag)
ans += hw[i].xf;
}
printf("%d", ans);
return 0;
}
并查集学习过,但还是没能灵活运用,基础基础…