题目链接: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 - 1131C. Birthday(贪心)题目链接题目给你n和n个数,要你重新排列n个数,使得这些数的相邻差值中最大的那个值最小。stat
暴枚最长桌脚的长度$l$,然后长度比$l$长的桌脚全部都要砍掉长度比$l$短的桌脚选择代价前$k$小的砍掉用线段树维护;示例程序 :typedef long l
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
Codeforces 185A - Plant 全测试点49个
题目大意:给出 n 个数字组成的序列,现在可以对数列进行多次操作,每次操作可以选择其中一段连续的数列,用其平均数替换原位置,换句话说,若原连续数列为 1 2 3,则可以替换为 2 2 2,问如何操作可以使得最后答案...
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
Codeforces 1105B - Zuhair and Strings 测试点37个(全)
Codeforces global round 10 codes
Codeforces round 678 division 2 codes
Some of the Codeforces problems codes
Codeforces - 1107B. Digital root & 1107C. Brutality(规律 & 贪心)Codeforces - 1107B.
Codeforces round 678 D2_Codeforces_源码
打codeforces的神器
一个Codeforces、牛客竞赛、AtCoder平台的编程竞赛查询插件,ACMer必备.zip
codeforces-js Codeforces JS
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done
使用 C# + WPF 开发 --- 还在发愁打了那么多场比赛都没有进入首页么? 还在为了前 5 的 hacker 名额阅读千份代码么? 是的,你没有看错! 这是一个 Edu & Div.3 轮 Open hacking 错误代码自动查找器!...