经济节约
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;
}
版权声明:本文为博主原创文章,未经博主允许不得转载。