題意#
給定一個整數 \( n \)，將 \( 1 \) 到 \( n \) 的數字拆分成兩個集合，
使兩個集合的數字總和相同。
如果能成功平分，輸出 YES 與兩組集合的內容；
若無法平分，輸出 NO。
思路#
第一步先檢查數字總和能否被平分。
\( 1 \) 到 \( n \) 的總和為 \( \frac{n(n+1)}{2} \)，
如果總和是奇數則無法平分，直接輸出 NO。
如果總和是偶數，就一定能找到平分的方法。
目標是從 \( n \) 個數字中挑出部分，使總和等於整體的一半。
這裡可以使用貪心策略，從數值最大的 \( n \) 開始往下挑選。
若當前數字加入第一堆不會超過目標值，就將其加入；
若會超過，就放入第二堆。
依序選到 1 後就能成功分好兩組。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n;
cin >> n; // 讀取數字 n
// 判斷 1~n 的總和是否為奇數，奇數無法平分
if ((n*(n+1)/2) & 1) cout << "NO\n";
else {
vector<int> a, b;
int sum = 0; // sum 紀錄第一堆目前累積的總和
// 從大到小遍歷 1~n 的數字，貪心地放入第一堆
for (int i = n; i > 0; i--) {
// 如果把 i 放進去不會超過總和的一半，就放進第一堆 a
if (sum + i <= n*(n+1)/2/2) sum += i, a.pb(i);
else b.pb(i); // 否則代表第一堆裝不下了，放進第二堆 b
}
cout << "YES\n" << sz(a) << '\n';
for (auto i : a) cout << i << ' ';
cout << '\n' << sz(b) << '\n';
for (auto i : b) cout << i << ' ';
cout << '\n'; // 依序印出兩堆集合的大小與內容
}
}
