Codeforces 388C Fox and Card Game(贪心）

题目链接：Codeforces 388C Fox and Card Game

题目大意：给出n叠牌，每叠牌有s[i]张，然后有两个人进行游戏，A只能从牌底拿牌，B只能从牌顶拿牌，那到牌的牌面总和即为的分，两人均按照最优的方式取牌，问说最后两人的得分。

解题思路：很像博弈题，但是可以用贪心做。首先对于每堆牌来说，要么奇数，要么偶数，偶数的时：两个各取一半，因为如果靠近A这边的一半牌里有很大牌面的数，那么A想取的这张牌要比B简单的多（即B拿不走这张牌，而且A同时可以对这张牌缓一缓，因为双方均均以最优方式），那么B就不会傻傻的去浪费步数争完全取不到的牌。奇数时：肯定有一方要多拿一张牌，那么谁拿走这张牌就要根据说所有奇数牌堆的中间牌大小决定的。

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;
const int N = 105;

int n, m, c[N], s[N];

bool cmp(const int& a, const int& b) {
	return a > b;
}

int main () {
	int cnt = 0, p = 0, q = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &m);
		int tmp = m / 2;
		for (int j = 0; j < m; j++) {
			scanf("%d", &c[j]);
			if (j < tmp) p += c[j];
			else q += c[j];
		}

		if (m & 1) {
			q -= c[tmp];
			s[cnt++] = c[tmp];
		}
	}

	sort(s, s + cnt, cmp);
	for (int i = 0; i < cnt; i++) {
		if (i & 1) q += s[i];
		else p += s[i];
	}

	printf("%d %d\n", p, q);
	return 0;
}

Codeforces 388C Fox and Card Game(贪心）

原文：http://blog.csdn.net/keshuai19940722/article/details/18986977