題目大意
把 $1 \sim n$ 這 $n$ 個數字分成兩堆,使得兩堆的總和相同。輸出無解或是構造一組解。
- $1 \leq n \leq 10^6$
題解
如果 $\sum\limits_{i = 1}^n i$ 為奇數,則顯然不能夠分成兩組使得總和相同。否則的話我們可以這樣構造一組解:
- 從 $n$ 到 $1$ 放入,每次放入總和比較小的那一堆。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
long long sum = n * (n + 1LL) / 2;
if(sum % 2 == 1) {
cout << "NO\n";
return 0;
}
long long sum_a = 0, sum_b = 0;
vector<int> a, b;
for(int i = n; i >= 1; i--) {
if(sum_a < sum_b) {
a.push_back(i);
sum_a += i;
} else {
b.push_back(i);
sum_b += i;
}
}
cout << "YES\n";
cout << a.size() << "\n";
for(auto x : a) {
cout << x << " \n"[x == a.back()];
}
cout << b.size() << "\n";
for(auto x : b) {
cout << x << " \n"[x == b.back()];
}
return 0;
}
如果本文對您有幫助的話幫忙點擊廣告和分享吧!
© 若無特別註明,本站文章皆由 WeakMouse's Coding Blog 原創 ,轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ,作者 ,並附上原文連結: 【題解】CSES - Two Sets
0 留言