经济节约

深藏阁楼爱情的钟 2022-08-14 05:50 137阅读 0赞

## 经济节约 ##

####  ####

##### Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

由于经济紧张，某国国王决定减少一部分多余的士兵，这些士兵在边界都有各自的管辖范围。例如，士兵x 的管辖范围\[a,b\]。我们定义：对于i号士兵，如果存在j号士兵的管辖范围\[a,b\], a<a且b<b成立，那么i号士兵就是多余的。给出多个士兵的管辖范围，问有多少个士兵是多余的？有多组数据，每组数据的第一行为一个整数n（1<=n<=100000）,下面n行每行包含两个整数a,b,代表i号士兵的管辖范围（0<=a<b<=200000）。所有的a是不同的，b也是不同的。

## 输出 ##

输出多余士兵的个数。<span font-family:\\'times="" new="" roman\\';="" \\"="">

## 示例输入 ##

5 
    0 10 
    2 9 
    3 8 
    1 15 
    6 11

## 示例输出 ##

## 提示 ##

## 来源 ##

fmh

## 示例程序 ##

#include<stdio.h>    
    #include<stdlib.h>    
    #define Maxsize 100000+10    
    struct node    
    {    
        int s,e;    
    }node[Maxsize];    
    int cmp(const void *a,const void *b)    
    {    
        return (*(struct node*)a).s>(*(struct node*)b).s?1:-1;    
    }    
    int main()    
    {    
        int a;    
        int i,t;    
        while(scanf("%d",&a)!=EOF)    
        {    
            int sum=0;    
            for(i=0;i<a;i++)    
            {    
                scanf("%d %d",&node[i].s,&node[i].e);    
            }    
            qsort(node,a,sizeof(node[0]),cmp);    
            t=node[0].e;    
            for(i=1;i<a;i++)    
            {    
                    
                if(node[i].e>t)    
                {    
                    t=node[i].e;    
                }    
                else    
                {    
                    sum++;    
                }    
            }    
            printf("%d\n",sum);    
        }    
    }