题解 | # C. Number Game #
对于Alice来说是满足单调性的，所以可以二分去找Alice的操作次数
因为
是越来越小且递减之间的差值为1
首先Alice的最优操作是将现在存在的所有数里面删除一个大于等于的数，最优的选择是删除最大的小于等于的数，这样直接删除最大的数，而不是删除最小的数，因为删除最大的数后面不会构成威胁
Bob的操作是将一个数加上，因为随着 i 增加是逐渐减去 1 的，例如现在为10，那么下一轮中为9，由此可得Bob的最优操作是将一个最小的数加上，这样这个数一定是不能被下一轮的Alice删除的，所以选择最小的数加上
我的错误想法：如果Bob将最小的数加上有可能被下一轮的Alice删除，所以得一直给最大的数加上
解释，Bob这一轮加上，下一轮Alice一定删除不了，因为递减一
那么用vector维护即可
总代码：
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define debug(x) cout << #x << "= " << x << endl;
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;
const int N = 100 + 10;
int n, a[N];
bool check(int x){
vector<int> v;
for(int i = 1; i <= n; i ++) v.push_back(a[i]);
for(int i = 1; i <= x; i ++){
int now = x - i + 1;
if(!v.size() || v[0] > now) return false;
auto it = upper_bound(v.begin(), v.end(), now) - 1;
v.erase(it);
if(v.size()) v[0] += now;
sort(v.begin(), v.end());
}
return true;
}
void solve(){
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
sort(a + 1, a + 1 + n);
int l = 0, r = n, ans = 0;
while(l <= r){
int mid = (l + r) / 2;
if(check(mid)){
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
cout << ans << endl;
return ;
}
signed main(){
HelloWorld;
int tt = 1;
cin >> tt;
while(tt --) solve();
return 0;
}
查看18道真题和解析
