Codefores 398A Cards(贪心+暴力）

本文主要是介绍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(贪心+暴力）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---