Codeforces gym 101243 E - Cupcakes

链接

http://codeforces.com/gym/101243/

题意

桌子上有K个蛋糕，有N个人排队吃蛋糕，其中N-1个人能吃的蛋糕个数为[1, ai]个，另一个吃的最多的人，他每次必吃ai个，如果轮到一个人时桌子前没蛋糕了，那么他要清理桌子，其他N-1个人都希望这个吃的最多的人清理桌子，问是否能使这个人清理桌子。第N个人吃完蛋糕后第一个人会继续去吃蛋糕，直到K = 0。

分析

令吃最多的人的位置为pos，吃的量为X，则第一次轮到他时，前面pos - 1个人能吃[pos - 1, ∑pos−1i=1ai ]个 ，如果K在这个区间内，则可以打成，第二次轮到时，能消耗的蛋糕区间为[N - 1 + X, ∑pos−1i=1ai+∑Ni=1ai ]个，以此类推， 如果K属于其中的任一区间，则输出”YES”。

#include <bits/stdc++.h>
using namespace std;
const int MAXN =  + ;
long long a[MAXN];

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int n;
    long long K;
    scanf("%d %lld", &n, &K);
    long long b = , s = , m = , pos = ;
    for (int i = ; i <= n; ++i)
    {
        scanf("%lld", &a[i]);
        if (a[i] >= m) m = a[i], pos = i;
        s += a[i];
    }
    s -= m;
    for (int i = ; i < pos; ++i)
    {
        b += a[i];
    }
    bool flag = false;
    if (K ==  && pos == ) flag = true;
    for (long long i = ; K > ; ++i)
    {
        long long down = (pos - ) + ((long long)n - L) * (i - L);
        long long up = b + s * (i - L);
        if (K < down)
        {
            break;
        }
        else if (K > up)
        {
            K -= m;
            continue;
        }
        else flag = true;
    }
    puts(flag ? "YES" : "KEK");
    return ;
}