首页 > 代码库 > Codeforces Round #228 (Div. 1) C 贪心
Codeforces Round #228 (Div. 1) C 贪心
嘎嘎,今天被一些事耽误了,可是还是A了几个题目,这道题还不错
题目链接:
题意:两个人玩游戏,有N堆纸牌,纸牌上有数字,A每次仅仅能取N堆中的 当中一个的顶部的 纸牌,B仅仅能取N堆中的当中一个底部 的纸牌,A。B都想让自己取的和最大,问最后比分为多少
画了一下。假设某一堆里的 纸牌数量为偶数,发现事实上是两个人各分一半,由于假设对方想从这里拿走本来属于自己那半部分的 较大的牌,自己全然来得及阻止的,
接下来就是奇数了,奇数 事实上先手者就抢到了中间的一张牌。另外两半还是各自一半,所以 应该以每一个奇数堆的 中间纸牌 的大小来进行贪心,
int n; typedef struct Node { int mid; int id; }; Node node[100 + 55]; int mp[100 + 55][100 + 55]; int ss[100 + 55]; void init() { memset(ss,0,sizeof(ss)); memset(node,0,sizeof(node)); } bool input() { while(cin>>n) { return false; } return true; } bool cmp(Node x,Node y) { return x.mid > y.mid; } void cal() { int ans1 = 0; int ans2 = 0; int cnt = 0; for(int i=0;i<n;i++) { scanf("%d",&ss[i]); if(ss[i]&1) { for(int j=1;j<=ss[i];j++) { scanf("%d",&mp[i][j]); if(j == (ss[i] + 1)/2) { node[cnt].id = i; node[cnt++].mid = mp[i][j]; } } } else { for(int j=1;j<=ss[i];j++) { int x; scanf("%d",&x); if(j <= ss[i]/2) ans1 += x; else ans2 += x; } } } sort(node,node + cnt,cmp); int mark = 1; for(int i=0;i<cnt;i++) { if(mark > 0) { int k = node[i].id; for(int j=1;j<=(ss[k] + 1)/2;j++) ans1 += mp[k][j]; for(int j=(ss[k] + 1)/2 + 1;j<=ss[k];j++) ans2 += mp[k][j]; } else { int k = node[i].id; for(int j=1;j<=ss[k]/2;j++) ans1 += mp[k][j]; for(int j=(ss[k] + 1)/2;j<=ss[k];j++) ans2 += mp[k][j]; } mark *= -1; } cout<<ans1<<" "<<ans2<<endl; } void output() { } int main() { while(true) { init(); if(input())return 0; cal(); output(); } return 0; }
Codeforces Round #228 (Div. 1) C 贪心
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。