# 【CSES】1161. Stick Divisions

## [題目連結](https://cses.fi/problemset/task/1161/)

## **時間複雜度**

* $O(NlogN)$

## **解題想法**

這題的想法很簡單，就是將過程反向操作，變成從最小的開始一個一個往 $x$ 合成，貪心的部分是每次取最小的的兩個並把他們結合之後，把結合出的長度在丟回待處理區，直到合成出長度是 $x$ 的木條

## **完整程式**

/* Question : CSES 1161. Stick Divisions */

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

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mem(x, value) memset(x, value, 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 = 2e5 + 50;
const int Mod = 1e9 + 7;
int x, n, res, tmp, a, b;
multiset<int> stick;

signed main(){
    opt;
    cin >> x >> n;
    for( int i = 0 ; i < n ; i++ ){
        cin >> tmp;
        stick.insert(tmp);
    }

    res = 0;
    while( stick.size() > 1 ){
        a = *stick.begin();
        stick.erase(stick.begin());
        b = *stick.begin();
        stick.erase(stick.begin());

        res += (a+b);
        stick.insert(a+b);
    }

    cout << res << "\n";
}