经济节约
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 <string.h>
#include <algorithm>
using namespace std;
struct node
{
int k;
int e;
}a[100005];
bool cmp(struct node a,struct node b)
{
return a.k < b.k;
if(a.k == b.k)
return a.e > b.e;
}
int main()
{
int n,m,i,j;
while(~scanf("%d",&n))
{
for(i = 0;i < n; i++)
{
scanf("%d %d",&a[i].k,&a[i].e);
}
sort(a,a+n,cmp);
int sum = 0;
j = 0;
for(i = 1;i < n; i++)
{
if(a[j].e < a[i].e)
{
j = i;
}
else
{
sum++;
}
}
printf("%d\n",sum);
}
}
#include <string.h>
#include <algorithm>
using namespace std;
struct node
{
int k;
int e;
}a[100005];
bool cmp(struct node a,struct node b)
{
return a.k < b.k;
if(a.k == b.k)
return a.e > b.e;
}
int main()
{
int n,m,i,j;
while(~scanf("%d",&n))
{
for(i = 0;i < n; i++)
{
scanf("%d %d",&a[i].k,&a[i].e);
}
sort(a,a+n,cmp);
int sum = 0;
j = 0;
for(i = 1;i < n; i++)
{
if(a[j].e < a[i].e)
{
j = i;
}
else
{
sum++;
}
}
printf("%d\n",sum);
}
}
代码菜鸟，如有错误，请多包涵！！