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

深藏阁楼爱情的钟 2022-12-19 13:22 90阅读 0赞

### [家庭作业][Link 1] ###

题目描述  
![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]  
输入格式  
第一行一个整数n ，表示作业的数量；  
接下来 n行，每行包括两个整数，第一个整数表示作业的完成期限，第二个数表示该作业的学分。  
输出格式  
输出一个整数表示可以获得的最大学分。保证答案不超过 C/C++ 的 int 范围

输入输出样例  
输入 \#1  
7  
1 6  
1 7  
3 2  
3 1  
2 4  
2 5  
6 1  
输出 \#1  
15  
说明/提示  
![题目][20201108094415105.png_pic_center]

--------------------

#### 思路一（有漏洞） ####

以第一关键字学分、第二关键字时间对 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;
    }

--------------------

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

[Link 1]: https://loj.ac/problem/10008
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/a853921a8dd341e28be87312cec012ed.png
[20201108094415105.png_pic_center]: /images/20221120/d1a187928b1b4d329cfa4514dc65d978.png