山东理工大学第七届ACM校赛-经济节约 分类: 比赛 2015-06-26 10:34 19人阅读 评论(0) 收藏

经济节约

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;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

上一篇:[译] Angular 2 VS. React: 血色将至


下一篇:python-其他常用模块