首页 > 代码库 > 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 贪心