基础算法题——家庭作业（并查集的标记法、贪心）

家庭作业

题目描述

输入格式
第一行一个整数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;
}

并查集学习过，但还是没能灵活运用，基础基础…