将21,22,...,2n分成数量相等的两堆,使两堆和的差值最小
数据也不大,挺简单的
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, a, b) for (register int i = a; i <= b; i++) int t, n; ll cnt[40]; int main() { cnt[1] = 2; rep(i, 2, 30) cnt[i] = cnt[i - 1] * 2; cin >> t; while (t--) { cin >> n; ll cnt1 = 0, cnt2 = 0, ans1 = 0, ans2 = 0; for (int i = n; i; i--) { if ((ans1 <= ans2 && cnt1 < n / 2) || cnt2 == n / 2) { cnt1++; ans1 += cnt[i]; } else { cnt2++; ans2 += cnt[i]; } } cout << abs(ans1 - ans2) << endl; } }
通过在原数组插值构建beautiful array。
题目一直在强调不需要最小化m。可以构造一个长度为k的数组,输出n次,不成立的情况是原数组的数的种类大于k。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, a, b) for (register int i = a; i <= b; i++) int t, k, n, a[110]; int vis[110], cnt; int main() { cin >> t; while (t--) { cin >> n >> k; cnt = 0; rep(i, 1, n) vis[i] = 0; rep(i, 1, n) { cin >> a[i]; if (!vis[a[i]]) { vis[a[i]] = 1; cnt++; } } if (cnt > k) puts("-1"); else { cout << k * n << endl; rep(i, 1, n) { rep(j, 1, n) if (vis[j]) cout << j << " "; for (int j = 1, id = 1; id <= k - cnt; j++) if (!vis[j]) { id++; cout << j << " "; } } cout << endl; } } }
Codeforces Round #638 (Div. 2)
原文:https://www.cnblogs.com/likunhong/p/12817470.html