本文主要是介绍SDUT 3273 经济节约（尺取），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem Description
由于经济紧张，某国国王决定减少一部分多余的士兵，这些士兵在边界都有各自的管辖范围。例如，士兵x 的管辖范围[ax,bx]。我们定义：对于i号士兵，如果存在j号士兵的管辖范围[aj,bj], aji且bij成立，那么i号士兵就是多余的。给出多个士兵的管辖范围，问有多少个士兵是多余的？Input
有多组数据，每组数据的第一行为一个整数n（1<=n<=100000）,下面n行每行包含两个整数ai,bi,代表i号士兵的管辖范围（0<=aii<=200000）。所有的ai是不同的，bi也是不同的。Output
输出多余士兵的个数。
Sample Input
5 0 10 2 9 3 8 1 15 6 11
Sample Output
3
来自菜鸡author：
这道题最开始看不懂题意，后来dalao讲才知道，就是给定坐标，找出一条坐标轴线上管辖区域重复的士兵而已。把每个士兵的右端点按重大到小排序，排序后第一个士兵的右端点坐标就是管辖区的最右端，下边各个士兵的右端点坐标都被包括在其中。再往下比较左端点坐标，记住第一个士兵左坐标，往后若比此坐标大的说明被包括在内，为多余的，计数。若小，则把左坐标更新为更小的，依次尺取。
这里边唯一坑的一个是坐标相等也会被包括内，因此还错了一发，惭愧。
AC代码如下：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct F
{int x;int y;
} f[100010];
bool cmp(struct F a,struct F b)
{return a.y>b.y;
}
int main()
{int n,s,i;int min;while(~scanf("%d",&n)){s=0;for(i=0; i<n; i++){scanf("%d %d",&f[i].x,&f[i].y);}sort(f,f+n,cmp);min=f[0].x;for(i=1; i<n; i++){if(f[i].x<min)min=f[i].x;elses++;}printf("%d\n",s);}return 0;
}
这篇关于SDUT 3273 经济节约（尺取）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
