12.28测试

T3
洛谷同题
这题需要找一下规律。
首先，Bessie必须先合成最中间的蛋糕，否则Elsie就会从离那个蛋糕最近的一段开始吃，最后一定能吃到那个蛋糕，这样Bessie就浪费了一次机会。
其次，Elsie可以掌握游戏的主动权，它往哪里吃，Bessie就必须往同样的方向合成蛋糕，这是显而易见的。
最后，Elsie一定吃掉

\frac{n}{2}-1

个蛋糕，Bessie一定吃掉

\frac{n}{2}+1

个蛋糕，这题就变为了求连续

\frac{n}{2}+1

个蛋糕的和的最小值（因为Elsie有主动权，他可以选择最优方案而给Bessie最差方案）。
Code:

CPP

#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;
}

文章操作

相关推荐

评论

12.28测试