【C++】競程筆記（algorithm 習題練習）

習題取自：NTUCPC Guide

此為個人解題過程，純粹紀錄。

---

1. https://tioj.ck.tp.edu.tw/problems/1287

一行測資輸入程式碼寫法：

for (int i=0;i<n;i++){
    int x;
    cin >> x;
    num.push_back(x);
}

宣告變數 x 放 for 裡面，然後讓 cin 去讀，在 push_back() 給 vector。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){

    int n;

    while (cin >> n){
        vector <int> num;

        for (int i=0;i<n;i++){
            int x;
            cin >> x;
            num.push_back(x);
        }

        sort(num.begin(), num.end());

        for (int i=0;i<num.size();i++){
            cout << num[i];
            if (i < num.size()-1){
                cout << " ";
            }
        }

        cout << "\n";
    }

    return 0;
}

2. https://zerojudge.tw/Submissions?language=CPP&problemid=k026#aria_CPP

中位數應用，要記得索引是從 0 開始，所以其實 n/2 就好，不用再 +1。

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> num(n);
    for (int i=0;i<n;i++){
        cin >> num[i];
    }
    
    if (n%2!=0){
        cout << num[n/2];
    }
    else{
        cout << (num[n/2-1] + num[n/2]) / 2;
    }
}

3. https://cses.fi/problemset/task/1621

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector <int> num;
    for (int i=0;i<n;i++){
        int x;
        cin >> x;
        num.push_back(x);
    }
    sort(num.begin(), num.end());
    auto it = unique(num.begin(), num.end());
    num.erase(it, num.end());
    cout << num.size();
    return 0;
}

unique()、erase() 練習。

用完 unique() 要記得 erase() 才會刪除元素，且要設定迭代器 it = unique() 給 erase() 的 begin()。

:::warning
注意：記得用 sort()，因為 unique() 是篩選相鄰相同的元素。
:::

4. https://tioj.ck.tp.edu.tw/problems/2193

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<unsigned int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    
    stable_sort(nums.begin(), nums.end(), [](unsigned int a, unsigned int b) {
        return __builtin_popcount(a) < __builtin_popcount(b);
    });
    
    for (int i = 0; i < nums.size(); ++i) {
        if (i > 0) cout << " ";
        cout << nums[i];
    }
    cout << endl;
    
    return 0;
}

sort() 自定義函數練習。

__builtin_popcount(int number)：是 GCC 編譯器內建的函數。此函數用於計算無號整數（unsigned int）二進位形式中 1 的數量。

然後這東東的參數只接受 >0 的 int 或 unsigned int。

// lambda 函數（匿名函數） -> 輕量化的函數形式
[](unsigned int a, unsigned int b) {
    return __builtin_popcount(a) < __builtin_popcount(b);
    // 若 a 二進位中的 1 數量比 b 少，則 true，否則 false。
}

a < b 的做法是因為題目要求如果數量相同，則維持原輸入測資的排序。