12.28测试

sunpeilun · 2025-01-18 08:37:44 · 个人记录

T3
洛谷同题
这题需要找一下规律。
首先，Bessie必须先合成最中间的蛋糕，否则Elsie就会从离那个蛋糕最近的一段开始吃，最后一定能吃到那个蛋糕，这样Bessie就浪费了一次机会。
其次，Elsie可以掌握游戏的主动权，它往哪里吃，Bessie就必须往同样的方向合成蛋糕，这是显而易见的。
最后，Elsie一定吃掉 \frac{n}{2}-1 个蛋糕，Bessie一定吃掉 \frac{n}{2}+1 个蛋糕，这题就变为了求连续 \frac{n}{2}+1 个蛋糕的和的最小值（因为Elsie有主动权，他可以选择最优方案而给Bessie最差方案）。
Code:

#include<iostream>
#include<cstring>
using namespace std;
int arr[1000001],t,n;
long long s[1000001],minn;
int main(){
    cin>>t;
    while(t--){
        minn=1e9*5e5;
        memset(s,0,sizeof(s));
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>arr[i];
            s[i]=s[i-1]+arr[i];
        }
        for(int i=0;i+n/2+1<=n;i++){
            minn=min(minn,s[i+n/2+1]-s[i]);
        }
        cout<<minn<<" "<<s[n]-minn<<endl;
    }
    return 0;
}