宁波市第32届中小学生程序设计竞赛（初中组）母鸡下蛋

本是古典何须时尚 2022-06-10 23:28 64阅读 0赞

问题 C: 母鸡下蛋  
  
鸡国中的母鸡最擅长下蛋了，MGMG 是鸡国中一只以下蛋产量高而闻名全鸡国的母鸡。  
鸡国专供下蛋的 n 个鸡窝呈一字排列在鸡国的“下蛋中心”，从左到右依次编号为 1 到n。每个鸡窝都有一个最大可下蛋的量，其中第 i 个鸡窝的最大可下蛋量为 ci 。有时候由于MGMG 产量实在太大而无法在一个鸡窝中下完所有的蛋，不得不转移到隔壁的鸡窝继续下蛋，如果隔壁的鸡窝还是不能让它下完所有的蛋，则 MGMG 继续转移，直到下完所有的蛋，或者向“下蛋中心”管理员投诉“鸡窝数量实在太少了，我一只鸡的下蛋量都装不下！”。  
为了节省转移时所耗费的体力，请你编程帮助 MGMG 找若干个连续的鸡窝(个数尽量少)，让它能下完所有的蛋。  
  
  
输入  
  
输入共 2 行。  
第 1 行输入两个整数 n 和 t，表示“下蛋中心”有 n 个可供下蛋的鸡窝，MGMG 一次总共要下 t 个鸡蛋。  
第 2 行 n 个正整数 ci (1≤i≤n)，依次表示第 i 个鸡窝最大可下蛋量为 ci 个。  
  
  
输出  
  
输出 1 行一个整数或一个单词。当输出整数时表示让 MGMG 下完所有的蛋至少需要几个连续的鸡窝。当 MGMG 用完所有的鸡窝都无法下完所有的蛋时，MGMG 表示非常愤怒，输出单词“Angry”（不包含双引号，注意大小写）。  
  
样例输入  
5 4  
1 2 1 2 3  
  
  
样例输出  
2

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    #include <map>
    #include <string>
    #include <stack>
    #define LL long long
    #define INF 0x7fffffff
    #define MAX 200010
    #define PI 3.1415926535897932
    #define E 2.718281828459045
    using namespace std;
    LL t,n;
    LL a[1000005];
    int main()
    {
        scanf("%lld%lld",&n,&t);
        LL sum=0,minn,start,endd;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            sum+=a[i];
        }
        if(sum<t) printf("Angry");
        else
        {
           sum=0;start=1;endd=1;
           while(sum<t)
           {
               sum+=a[endd];
               endd++;
           }
           minn=endd-start;
           while(sum>=t)
           {
               sum-=a[start];
               start++;
               while(sum<t)
               {
                   sum+=a[endd];
                   endd++;           //endd到n+1时不能再继续加了 否则进入死循环
                   if(endd==n+2) break;   //正常到n+1  所以当endd到n+2时应该跳出循环
               }
               minn=min(minn,endd-start);
           }
    
            printf("%lld",minn);
        }
    
        return 0;
    }