【CSES】1092. Two Sets

題目連結

時間複雜度

$O (N)$

解題想法

這題是一題比較裸的貪心題，只要簡單想一下條件就會發現他其實很好處理

簡單敘述一下這題的核心解題思路

先算出
$S_{N}$ 的和
從題目中可以知道，兩個數列的元素和會相等且都會是
$\frac{S_{N}}{2}$ ，所以只要對這點下去做貪心就可以解決掉這題了

貪心用法：

從

N

開始往下看，如果其中一個序列放得進去不會超過

\frac{S_{N}}{2}

就放，否則放另一邊

完整程式

在實作的時候要比較需要注意一下

∵ 0 \leq N \leq 10^{6}

∴

要將變數開成 long long














































/* Question : CSES 1092. Two Sets */

#include<bits/stdc++.h>
using namespace std;

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mem(x) memset(x, 0x3F, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define f first
#define s second
#define int long long

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 1e8 + 50;
const int Mod = 1e9 + 7;
int mid, sum, n;
vector<int> le;
vector<int> ri;

signed main(){
    opt;
    cin >> n;
    if( (n * (n+1)) % 4 == 0 ){
        sum = n * (n+1) / 2;
        int l_val = sum / 2;
        int r_val = sum / 2;
        for( int i = n ; i > 0 ; i-- ){
            if( l_val - i >= 0 ){
                le.push_back(i);
                l_val -= i;
            }else{
                ri.push_back(i);
                r_val -= i;
            }
        }
        cout << "YES\n";
        cout << le.size() << "\n";
        for( auto i : le ) cout << i << " ";
        cout << "\n" << ri.size() << "\n";
        for( auto i : ri ) cout << i << " ";
        cout << "\n";
    }else{
        cout << "NO\n";
    }
}