HRBUST - 2080 链条-------HPU组队选拔赛（三）

ゞ浴缸里的玫瑰 2022-05-26 11:16 154阅读 0赞

HRBUST - 2080 链条-[点击打开链接][Link 1]

<table> 
 <tbody> 
 <tr> 
 <td>链条</td> 
 </tr> 
 <tr> 
 <td> 
 <table> 
 <tbody> 
 <tr> 
 <td>Time Limit: 1000 MS</td> 
 <td>Memory Limit: 32768 K</td> 
 </tr> 
 </tbody> 
 </table> 
 <table> 
 <tbody> 
 <tr> 
 <td>Total Submit: 163(49 users)</td> 
 <td>Total Accepted: 64(44 users)</td> 
 <td>Rating: <img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""></td> 
 <td>Special Judge: No</td> 
 </tr> 
 </tbody> 
 </table></td> 
 </tr> 
 <tr> 
 <td>Description</td> 
 </tr> 
 <tr> 
 <td>给出n对数字，每个对数字由两个数a和b构成，其中a&lt;b，现在用一些对拼成最长的链，要使得 b1 &lt; a2, b2 &lt; a3 ... 求最长链的长度。 </td> 
 </tr> 
 <tr> 
 <td>Input</td> 
 </tr> 
 <tr> 
 <td>有多组测试数据。 每组测试数据的第一行有一个数字N(1&lt;=N&lt;=10^5)。 接下来有n对数字ai和bi，数据保证保证ai&lt;bi，0&lt;=ai,bi&lt;=10^9。 处理到文件结束。 </td> 
 </tr> 
 <tr> 
 <td>Output</td> 
 </tr> 
 <tr> 
 <td>对于每组测试数据输出一行，为最长长度。 </td> 
 </tr> 
 <tr> 
 <td>Sample Input</td> 
 </tr> 
 <tr> 
 <td><pre>5
2 3
0 9
2 8
1 6
0 1
7
5 8
30 93
66 69
17 32
47 72
68 80
23 49
</pre></td> 
 </tr> 
 <tr> 
 <td>Sample Output</td> 
 </tr> 
 <tr> 
 <td><pre>2
3
</pre></td> 
 </tr> 
 </tbody> 
</table>

/*
 	活动安排问题的模板题 
 	
 */
 
 #include<cstdio>
 #include<algorithm>
 #include<cstring>
 #include<cmath>
 using namespace std;
 
 const int maxn=1e5+5;
 
 struct node{
 	int x,y;
 }a[maxn]; 
 
 bool cmp(node a,node b)
 {
 	return a.y==b.y?a.x<b.x:a.y<b.y;
 }
 
 
 int main()
 {
 	int n;
 	while(~scanf("%d",&n))
 	{
 		for(int i=0;i<n;i++)	scanf("%d %d",&a[i].x,&a[i].y);
 		sort(a,a+n,cmp);
 		int ans=1;
 		int z=a[0].y;
 		for(int i=1;i<n;i++)
 		{
 			if(a[i].x>z)
 			{
 				ans++;
 				z=a[i].y;
 			}
 		}
 		printf("%d\n",ans);
 	}
 	return 0;
 }

[Link 1]: http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=2080