codeforces错题（最小值最大化）

Problem - 1987D - Codeforces

爱丽丝和鲍勃正在玩一个游戏。最初有 n 个蛋糕，其中 i 个蛋糕的美味值为 ai。

爱丽丝和鲍勃轮流吃蛋糕，爱丽丝先吃：

• 在这一轮中，爱丽丝会选择并吃掉剩下的任何一个蛋糕，只要这个蛋糕的美味度严格地大于她之前吃过的蛋糕的最大美味度。注意，在第一轮，她可以选择任何蛋糕。
• 在鲍勃的回合中，他可以选择任何剩下的蛋糕并吃掉它。

当当前玩家无法吃到合适的蛋糕时，游戏结束。假设 x 是爱丽丝吃掉的蛋糕数量。那么，爱丽丝希望最大化 x ，而鲍勃希望最小化 x 。

求如果双方都以最优方式下棋，爱丽丝会吃掉多少个蛋糕？

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
typedef pair<ll, ll> PII;
#define pb emplace_back
//#define int ll
#define all(a) a.begin(),a.end()
#define x first
#define y second
#define ps push_back
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define INF 0x7fffffff

void solve();

const int N = 1e6 + 10;


signed main() {
    IOS;
    ll t;
    cin >> t;
    while(t--)
    solve();
    return 0;
}

void solve() {
    ll nn;
    cin >> nn;
    vector<ll> a(nn + 1);
    map<ll, ll> mp;
    for (int i = 1; i <= nn; ++i)
    {
        ll x;
        cin >> x;
        mp[x]++;
    }


    for(auto &[k,v] : mp)
        a.pb(v);
    ll n = a.size();

    vector<ll> dp(n+1,INF);
    dp[0] = 0;
    for(int i = 1; i <= n; ++ i)
    {
        vector<ll> ndp = dp;
        for(int k = 1; k <= n; ++ k)
        {
            ll nv = dp[k-1] + a[i-1];
            if(nv <= i - k)
            {
                ndp[k] = min(ndp[k],nv);
            }
        }
        dp = ndp;
    }
    ll ans = n;
    while(dp[ans] >= INF) ans--;
    cout << n - ans << endl;
}

以下是带注释的代码，对于男孩来说，要吃的话，理想的效果是把这个尺寸的都吃了，这样女孩就吃不到这个尺寸了。（这里的切入点是什么） 

void solve() {
    vector<int> a; // 存储蛋糕的美味度
    {
        int n;
        cin >> n;
        
        map<int, int> cnt; // 记录每个美味度的蛋糕数量
        while (n--) {
            int x;
            cin >> x;
            cnt[x]++;
        }
        
        for (auto const &[k, v]: cnt) {
            a.push_back(v); // 将蛋糕数量按美味度顺序存入数组a
        }
    }
    
    int n = a.size(); // 蛋糕种类数
    vector<int> dp(n + 1, inf); // dp[i]表示吃掉前i种蛋糕时，爱丽丝最多能吃多少个蛋糕
    dp[0] = 0;
    
    for (int i = 1; i <= n; i++) {
        vector<int> ndp = dp; // 临时存储新的dp值
        
        for (int k = 1; k <= n; k++) {
            int nv = dp[k - 1] + a[i - 1]; // 计算吃掉第i种蛋糕后，爱丽丝能吃到的蛋糕总数
            
            if (nv <= i - k) { // 如果当前选择不违反游戏规则
                ndp[k] = min(ndp[k], nv); // 更新dp值
            }
        }
        
        dp = ndp; // 更新dp数组
    }
    
    int ans = n; // 初始化答案为蛋糕种类数
    while (dp[ans] >= inf) ans--; // 找到最小的满足条件的ans值
    cout << n - ans << nl; // 输出爱丽丝最多能吃到的蛋糕数
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
    
    int T;
    cin >> T;
    while (T--) solve(); // 处理多组测试数据
}