G - 我怀疑这游戏里根本没有五星

蔚落 2022-03-21 07:12 89阅读 0赞

### 题目描述： ###

fgo有N个卡池，从左到右依次编号为1,2,3…N。  
一天,小明看着自己号里的圣晶石，决定试着抽一抽。因为石头不多，他决定找几个连续的卡池（从a到b，包括a和b），每个卡池抽一次（玄学）。然而并没有出货，于是他决定再找几个连续的卡池重复这一动作。  
重复了N次之后，小明不仅没有抽到一个五星从者，还花光了所有的圣晶石。 小明现在想知道他到底在每个卡池里分别抽了多少次。  
（这是一个玄不改非，氪不改命的故事）

Input  
每个测试实例第一行为一个整数N,(N <= 100000).接下来的N行，每行包括2个整数a b(1 <= a <= b <= N)。  
当N = 0，输入结束。  
Output  
每个测试实例输出一行，包括N个整数，第I个数代表小明抽第I个卡池的次数  
Sample Input  
3  
1 1  
2 2  
3 3  
3  
1 1  
1 2  
1 3  
0  
Sample Output  
1 1 1  
3 2 1

##### 分析： #####

本题看上去很简单，先开一个数组，全部置位0，然后在每次输入a，b的时候，将下标为a，下标为b中的值加1。  
最后输入就好了。  
代码如下：

#include"stdio.h"
    #include"string.h"
    int main()
    {
        int N;
        int a[100001];
        int i;
        int j,m;
        while(~scanf("%d",&N))
        {
            if(N==0)
                break;
            for(i=1; i<=N; i++)
                a[i]=0;
            m=N;
            while(N--)
            {
    
                scanf("%d%d",&i,&j);
                for(i; i<=j; i++)
                    a[i]++;
            }
            for(i=1; i<m; i++)
                printf("%d ",a[i]);
            printf("%d\n",a[i]);
        }
    }

可是这样因为数据过大，超时。  
只能换种方法考虑，我们发现，其实完全没必要依次给下标为a，b里面的元素赋值。  
我们可以在输入a，b的时候，将下标为a里面的值加1，下标为b+1里面的值减1。具体看代码：  
AC代码：

#include"stdio.h"
    #include"string.h"
    int main()
    {
        int N;
        int a[100001];
        int i;
        int j,m,sum;
        while(~scanf("%d",&N))
        {
            if(N==0)
                break;
            for(i=1; i<=N; i++)
                a[i]=0; //初始化为0
            m=N;sum=0;
            while(N--)
            {
    
                scanf("%d%d",&i,&j);//输入
                a[i]+=1;      
                a[j+1]-=1;
            }
         
            for(i=1; i<m; i++)
                {
                    sum+=a[i];
                    printf("%d ",sum);
                }
            printf("%d\n",sum+a[i]);
        }
    }