【題解】CSES - Two Sets

題目連結

題目大意

把 $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