【思维】Cupcakes Gym - 101243E

分手后的思念是犯贱 2022-06-09 02:13 118阅读 0赞

Think:  
1知识点：思维  
2题意：n个学生去吃纸杯蛋糕，每次可以吃\[1, ai\]个，循环队列，一直到将蛋糕吃光，有一个懒惰的家伙，每次吃ai个，如果不足ai个则将其吃光，懒惰家伙的ai值是序列里最大的，规则时第一个吃蛋糕之前发现纸杯蛋糕没有的学生需要打扫卫生(蛋糕数量为0时由序列内的第一个学生打扫卫生)，询问是否有可能使得懒惰的家伙打扫卫生  
3分析：思维题，维护一个区间\[l, r\]，表示到达懒惰的家伙位置的可能蛋糕数量，再次到达懒惰的家伙开始吃蛋糕的时候存在最小值和最大值，通过最小值和最大值维护更新这个区间，如果蛋糕数量在某一个状态位于区间内则表明有可能使得这个懒惰的家伙来打扫卫生，如果不可能使得蛋糕数量位于某一个区间内则说明懒惰的家伙没有可能打扫卫生  
4反思：  
1>注意数据范围，中间是否可能爆int  
2>注意初始维护的区间范围(懒惰的家伙吃蛋糕时不足ai个蛋糕，只要懒惰的家伙有蛋糕可以吃，则由序列内其下一个即第一个吃蛋糕之前发现蛋糕没有的学生来打扫卫生)

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    LL a[101400];
    
    int main(){
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        int n, m, i;
        LL mar, mil, mav, v, l, r;
        while(~scanf("%d %d", &n, &m)){
            mav = 0, mar = 0, mil = 0;
            for(i = 1; i <= n; i++){
                scanf("%lld", &a[i]);
                if(a[i] > mav){
                    mav = a[i], v = i;
                }
                mar += a[i];
            }
            mil = mav + (n-1);
            r = 0;
            for(i = 1; i <= n; i++){
                if(i < v)
                    r += a[i];
                else
                    break;
            }
            l = v - 1;
            bool flag;
            while(true){
                if(m >= l && m <= r){
                    flag = true;
                    break;
                }
                else if(m < l){
                    flag = false;
                    break;
                }
                l += mil;
                r += mar;
            }
            if(flag)
                printf("YES\n");
            else
                printf("KEK\n");
        }
        return 0;
    }

[vjudge]: https://vjudge.net/problem/Gym-101243E