AtCoder Beginner Contest 270 D(dp) E(二分)

D. Stones (DP)

DP[n] = the number of stones that the first player can take if the game starts with a pile with n stones

\[dp[n] = \max (A_i + (n - A_i) - dp[n - A_i] | A_i <= n)\]

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    for (int i = 0; i < k; i++)
    {
        cin >> a[i];
    }

    vector<int> dp(n + 1);
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <k; j++)
        {
            if (i >= a[j])
            {
                dp[i] = max(dp[i], i - dp[i - a[j]]);
            }
        }
    }

    cout << dp[n] << endl;

    return 0;
}

E. Apple Baskets on Circle (二分)

二分搜索, 先确定需要多少轮次才能吃到至少 $k$ 个苹果, 复杂度 $O(N\log K)$

确定轮次之后, 再 $O(N)$ 确定每个盘子的剩余苹果数量

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    long long n, k;
    cin >> n >> k;

    vector<long long> a(n);
    for (long long i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    auto check = [&](long long mid)
    {
        long long temp = 0;
        for (long long i = 0; i < n; i++)
        {
            temp += min(a[i], mid);
        }

        return temp <= k;
    };

    long long l = 0, r = k + 1;
    long long need = -1;
    while (l <= r)
    {
        long long mid = (l + r) >> 1;
        if (check(mid))
        {
            l = mid + 1;
            need = mid;
        } else {
            r = mid - 1;
        }
    }

    assert(need >= 0);
    for (long long i = 0; i < n; i++)
    {
        k -= min(a[i], need);
        a[i] -= min(a[i], need);
    }
    for (long long i = 0; i < n; i++)
    {
        if (k > 0 && a[i] > 0)
        {
            a[i] -= 1;
            k -= 1;
        }
        cout << a[i] << " \n"[i == n - 1];
    }

    return 0;
}