本文主要是介绍Codeforces Round 916 (Div. 3) E1. Game with Marbles（博弈论*1400），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
感觉很难想。
如果你直接想的话，你就会发现有很多做法可以选择，而你根本不知道应该选哪个。
这时候可以先假设鲍勃已经取走了爱丽丝的所有的颜色的弹珠，（并且以每个颜色一个弹珠的代价）。
这时候每一项得分就是 S i = − ( b i − 1 ) S_i = -(b_i - 1) Si=−(bi−1)。
然后我们使得这时候爱丽丝的操作为取回弹珠，即她可以选择一种颜色的弹珠，并且直接取回，鲍勃的操作为选择一种颜色的弹珠，并且进行保留，使得爱丽丝无法取回这个颜色的弹珠。
那么当爱丽丝取回一次之后，就会使得当前的分数 S i 2 = S i + ( a i + b i − 1 ) S_{i2} = S_i + (a_i + b_i - 1) Si2=Si+(ai+bi−1)，因为她取回的时候会连带着鲍勃本身就有的取走（呼应本来的题目要求）。
这时候我们发现，如果我们选择 ( a i + b i ) (a_i + b_i) (ai+bi)更大的组合的话，就能够获得更多的收益。
这时候这个想法也可以呼应回原本的题目。
按照 ( a i + b i ) (a_i + b_i) (ai+bi)从大到小排序之后，两者都去选择更靠前的颜色i进行操作。
void solve(){int n;cin >> n;vector<pii>s(n+1);for(int i = 1;i <= n;i++)cin >> s[i].first;for(int i = 1;i <= n;i++)cin >> s[i].second;sort(s.begin()+1,s.end(),[&](pii a,pii b){return a.first + a.second > b.first + b.second;});long long ans = 0;for(int i = 1;i <= n;i++){if(i&1)ans += s[i].first - 1;else ans -= s[i].second - 1;}cout << ans << endl;
}
这篇关于Codeforces Round 916 (Div. 3) E1. Game with Marbles（博弈论*1400）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
