题解 | #D-预知#

一个问题，按照出题人的题解

void solve(){
    int n;
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    if(n==1){
        cout<<"-1\n";
        return ;
    }
    sort(a.begin(),a.end(),greater<int>());
    int m1=a[0];
    int m2=a[1];
    if(m1==1){
        cout<<0<<"\n";
        return ;
    }
    if(m2==1){
        cout<<m1-1<<"\n";
        return ;
    }
    cout<<m1<<"\n";
}

但实际上，我有一个疑问，预测最多的那一堆的牌，仍是不可行的，见下图

因为我是随机的，有可能我 8 种牌，翻出了 8 张，但这 8 张，恰好是 如此以来，编号是的牌，我还剩下张！ 这样，我随机翻牌，如果翻出了张中的张，怎么办？它们都是花色，重复了呀～

对于我的疑问，求解

另外给出了一个我自认为是正确的算法

void solve() {
    int n;
    cin >> n;

    vector<i64> a(n, 0);
    for (auto &x : a) cin >> x;

    if (n == 1) {
        cout << "-1\n";
        return;
    }

    sort(a.begin(), a.end());

    auto check = [&](i64 x) -> bool {
        auto b = a;
        i64 d = x / n, r = x % n;

        for (auto &y : b) y -= d;

        bool ok = true;
        for (auto y : b) {
            if (y >= 2) {
                ok = false;
                break;
            }
        }
        if (ok) return true;
        
        i64 extra = 0;
        for (auto y : b) {
            if (y >= 1) extra += (y - 1);
        }
        if (r >= extra) return true;

        return false;
    };

    i64 l = 0, r = 2e14;
    while (l < r) {
        i64 mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    i64 ans = l;
    cout << ans << "\n";
}

我的算法思路是，二分翻的张数，然后 check 一下这个 x 可不可行 因为是随机的，check 可行的方案，当且仅当一种花色的牌全部取完，或者是这种花色剩下一张，其他花色都是恰好只剩下一张

然后二分求解

我不知道我这种想法错在哪里，出题人回答一下，谢谢～