经济节约
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
由于经济紧张，某国国王决定减少一部分多余的士兵，这些士兵在边界都有各自的管辖范围。例如，士兵x 的管辖范围[ax,bx]。我们定义：对于i号士兵，如果存在j号士兵的管辖范围[aj,bj], aj<ai且bi<bj成立，那么i号士兵就是多余的。给出多个士兵的管辖范围，问有多少个士兵是多余的？
输入
有多组数据，每组数据的第一行为一个整数n（1<=n<=100000）,下面n行每行包含两个整数ai,bi,代表i号士兵的管辖范围（0<=ai<bi<=200000）。所有的ai是不同的，bi也是不同的。
输出
输出多余士兵的个数。
示例输入
5 0 10 2 9 3 8 1 15 6 11
示例输出
3#include <stdio.h>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int Max=101000; struct node
{
int a;
int b;
}line[Max];
bool cmp(node a,node b)
{
if(a.a<b.a)
{
return true;
}
else if(a.a==b.a&&a.b<b.b)
{
return true;
}
return false;
}
int main()
{
int n;
int bb;
int sum;
while(~scanf("%d",&n))
{
for(int i=0;i<n;i++)
{
scanf("%d %d",&line[i].a,&line[i].b);
}
sort(line,line+n,cmp);
bb=line[0].b;
sum=0;
for(int i=1; i<n; i++)
{ if(bb<line[i].b)
{
bb=line[i].b;
}
else
{
sum++;
}
}
cout<<sum<<endl;
}
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。