Codefores 398A Cards(贪心+暴力）

题目链接：Codefores 398A Cards

题目大意：给出a和b，表示说有a个“o”的卡和b个“x”的卡，将这a+b个卡片排成一个序列，每连续的k个相同的卡片为一个数，表示k^2，如果是o，则是+k^2，否则-k^2。要求找到一个序列使得最后的结果尽量大。

解题思路：一开始一直想用贪心的思想直接构造出来，后来和小伙伴一人想了一种构造方法，但是又互相推翻了。。。。不过很快就想到了暴力，因为b最多1e5，答案肯定要让o尽量在一起，x尽量分开，这样我们每次拿出一个o的卡片就可以让x被多分成一份，所以枚举x被分成的份数，贪心，尽量让o在一起。

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

using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll a, b, ans, v = 1;

ll solve (ll k) {
	ll x = b/k, c = b%k;
	ll ans = (a-k+2)*(a-k+2) +(k-2);
	ll tmp = c*(x+1)*(x+1) + (k-c)*x*x;
	return ans - tmp;
}

void put() {
	cout << ans << endl;

	ll x = b/v, c = b%v;
	bool flag = false;
	for (ll i = 1; i < v; i++) {
		if (flag) printf("o");
		for (ll j = 0; j < x; j++) printf("x");
		if (i <= c) printf("x");
		flag = true;
	}
	for (ll i = 0; i < (a-v+2); i++) printf("o");
	for (ll i = 0; i < x; i++) printf("x");
	printf("\n");
}

int main () {
	ans = -INF;
	cin >> a >> b;

	if (a == 0) {
		cout << b*b*(-1) << endl;
		for (ll i = 0; i < b; i++) printf("x");
		printf("\n");
		return 0;
	}

	for (ll i = 2; i <= a + 1; i++) {
		ll t = solve(i);
		if (t > ans) {
			ans = t; v = i;
		}
	}

	put();
	return 0;
}

Codefores 398A Cards(贪心+暴力）,布布扣,bubuko.com

Codefores 398A Cards(贪心+暴力）

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