AcWing蛋糕游戏

6118. 蛋糕游戏 - AcWing题库

a先手，每回合合并两个蛋糕,当只剩下一个蛋糕时最后吃掉

b后手,每回合吃最左边或最右边的蛋糕

求ab能吃的最多的值

a最多能吃n/2+1个,b吃n/2-1个,如果吃到a合并的蛋糕，获得的值还能更大，因此让a吃最小的n/2+1个，b获得剩下的

#include <bits/stdc++.h> #define fi first #define se second #define endl '\n' using namespace std; using LL = long long; const int mod = 1e9 + 7; const int N = 5e5 + 10,T = 20; int n; LL a[N]; void solve() { cin >> n; int len = n / 2 + 1; for (int i = 1;i <= n;i ++) cin >> a[i],a[i] += a[i - 1]; LL sa = a[n]; for (int i = 1;i + len - 1<= n;i ++) { int j = i + len - 1; sa = min(sa,a[j] - a[i - 1]); } cout << sa << " " << a[n] - sa << endl; } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int _ = 1; cin >> _; while(_--) solve(); return 0; }