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 ;
}