本文主要是介绍Codeforces Contest 389 E Fox and Card Game —— 贪心,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
This way
题意:
给你几堆数,第一个人可以从某一堆数最左边取出一个数,第二个人可以从某一堆数最右边取出一个数。每个人尽可能的想让自己拿到的数最大,第一个人开始拿,问你最终他们拿到的数的和。
题解:
一道贪心的博弈题。为什么可以贪心?因为左边的人只能拿左边的数,右边的人只能拿右边的数,因为是想让自己的数最大,所以需要让对方拿的数最小,那么当对方可以越过半数这个鸿沟拿到更大的数的时候,另一个人就可以阻止他。所以对于奇数个数的时候,就将最中间的数放到vector中让两个人贪心的轮流拿
#include<bits/stdc++.h>
using namespace std;
vector<int>vec;
int main()
{int n;scanf("%d",&n);int k,a1=0,a2=0;for(int i=1;i<=n;i++){scanf("%d",&k);int pre=0,en=0,a;for(int i=1;i<=k;i++){scanf("%d",&a);if(i<=k/2)a1+=a;if(i>(k+1)/2)a2+=a;if(k%2&&i==k/2+1)vec.push_back(-a);}}sort(vec.begin(),vec.end());for(int i=0;i<vec.size();i++){if(i%2)a2-=vec[i];elsea1-=vec[i];}printf("%d %d\n",a1,a2);return 0;
}
这篇关于Codeforces Contest 389 E Fox and Card Game —— 贪心的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!