# Week 8：排序三、二分搜

###### tags: `S3 公開資源`

:::info
時間：03/19 9:00 ~ 17:00
地點：成大計算機與網路中心 **75201** 教室
主題：排序三、二分搜
直播連結：https://youtube.com/live/8OJJqBkUif0?feature=share
:::

# 必作題題解

[TOC]

## 二章 - 第七節

<!-- ### [題目](連結) -->

### [UVa 11286 - Conformity](http://domen111.github.io/UVa-Easy-Viewer/?11286)

撰寫者：Jun-an

這題要找出最受歡迎的「課程組合」的人數。

假設某個學生選了 $100$ $101$ $102$ $103$ $488$ 這五門課，
那麼選課組合就是 「$100$ $101$ $102$ $103$ $488$」。

不過每個課程組合都沒有照順序排，
因此計算每個課程組合有多少人選之前要先排序。

至於課程組合的部分，可以發現都是由 $5$ 個長度為 $3$ 的數字組成，
所以可以直接用 $long$ $long$ $int$ 儲存，或是你要用 $string$ 也行。

接著是要計算最受歡迎的課程組合，
排序過後會發現一樣的課程組合會排在一起，
因此只需要用一次 $for$ 迴圈掃過即可。

這裡補充一下，如果出現多種最受歡迎組合的選課人數一樣時，
需要全部加總。

:::spoiler 參考程式碼

#include <iostream>
#include <algorithm>

using namespace std;

int course[10005][5];
long long save[10005];

int main() {
    int n;

    while (cin >> n && n != 0) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 5; ++j) {
                cin >> course[i][j];
            }

            sort(course[i], course[i] + 5);

            for (int j = 0; j < 5; ++j) {
                save[i] = save[i] * 1000 + course[i][j];
            }
        }

        sort(save, save + n);

        int mx = 1, cnt = 1, res = 1;

        for (int i = 1; i < n; ++i) {
            if (save[i] == save[i - 1]) {
                ++cnt;

                if (i == n - 1) {
                    if (cnt > mx) {
                        mx = cnt;
                        res = cnt;
                    }
                    
                    else if (cnt == mx) {
                        res += cnt;
                    }
                }
            }
            
            else {
                if (cnt > mx) {
                    mx = cnt;
                    res = cnt;
                }
                
                else if (cnt == mx){
                    res += cnt;
                }

                cnt = 1;
            }
        }

        cout << res << '\n';

        // clear.
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 5; ++j) {
                course[i][j] = 0;
            }

            save[i] = 0;
        }
    }
}

:::

---

### [Kattis sidewayssorting - Sideways Sorting](https://open.kattis.com/problems/sidewayssorting)

撰寫者：小麥

字串先存陣列再做旋轉，這個時候可以排序，之後在去旋轉回來。

:::spoiler

#include <bits/stdc++.h>

using namespace std;

vector<string> arr;
vector<string> arr_rotated;

void solve() {
    int n, m;
    while(true) {
        arr.clear();
        arr_rotated.clear();

        cin >> n >> m;
        if (n == 0 || m == 0) {
            return;
        }

        arr.resize(n);
        arr_rotated.resize(m);

        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n; i++) {
                arr_rotated[j] += arr[i][j];
            }
        }
        
        sort(arr_rotated.begin(), arr_rotated.end(), [](string x, string y) {
            for (int i = 0; i < x.length(); i++) {
                char x_lower = tolower(x[i]);
                char y_lower = tolower(y[i]);
                if (x_lower == y_lower) {
                    continue;
                }
                return x_lower < y_lower;
            }
            return false;
        });

        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                cout << arr_rotated[i][j];
            }
            cout << '\n';
        }
    }
}

int main() {
    solve();

    return 0;
}

:::

---

### [Kattis Sort of Sorting](https://open.kattis.com/problems/sortofsorting)

撰寫者：Eason

用內建sort寫cmp

:::spoiler 參考程式碼

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

bool cmp(string a, string b){
    if (a[0] == b[0]){
        if (a[1] == b[1]){
                return false;
        }
        else{
                return a[1] < b[1];
        }
    }
    else{
        return a[0] < b[0];
    }
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    while (cin >> n){
        if (n == 0) break;
        string name[205];
        for (int i = 0; i < n; i++){
                cin >> name[i];
        }
        stable_sort (name, name + n, cmp);
        for (int i = 0; i < n; i++){
                cout << name[i] << '\n';
        }
        cout << '\n';
    }
    return 0;
}

:::

---

## 二章 - 第八節

### [No - Judge 出現與否](https://hackmd.io/@sa072686/cp/%2FUEA2CFbIRqGvA_c9yaCP6Q#出現與否)

撰寫者：Eason

排序後直接二分搜

:::spoiler 參考程式碼

#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int n, q;
    cin >> n >> q;
    long long arr[100005];
    for (int i = 0; i < n; i++){
        cin >> arr[i];
    }
    sort (arr, arr + n);
    for (int i = 0; i < q; i++){
        long long temp, l = 0, r = n - 1;
        cin >> temp;
        while (l <= r){
            int mid = (l + r) / 2;
            if (temp == arr[mid]){
                cout << "YES\n";
                break;
            }
            else if (l == r){
                if (arr[mid] != temp) cout << "NO\n";
                else cout << "YES\n";
                break;
            }
            else if (temp < arr[mid]){
                r = mid - 1;
            }
            else if (temp > arr[mid]){
                l = mid + 1;
            }
        }
    }
    return 0;
}

:::

---

### [TOJ 47 - PB magic spell](https://toj.tfcis.org/oj/pro/47/)

撰寫者：Koying

二分搜 $a, b$

:::spoiler Code

#define MAXN 1000005
#define MAXM 1000005 
int n, m;
int x[MAXN];

void sol() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> x[i];
    sort(x, x + n);
    cin >> m;
    while (m--) {
        int k;
        cin >> k;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (x[mid] >= k)
                r = mid - 1;
            else
                l = mid;
        }

        if (l != n - 1 && x[l + 1] == k) {
            cout << k << '\n';
            continue;
        }
        else if (x[l] < k)
            cout << x[l] << ' ';
        else
            cout << "no ";

        r = n - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (x[mid] <= k)
                l = mid + 1;
            else
                r = mid;
        }

        if (x[r] > k)
            cout << x[r] << '\n';
        else
            cout << "no\n";
    }
}

:::

---

### [UVa 10282 - Babelfish](http://domen111.github.io/UVa-Easy-Viewer/?10282)

撰寫者：Jun-an

利用字串大小進行排序，接著使用二分搜。

:::spoiler 參考程式碼

#include <iostream>
#include <algorithm>

using namespace std;

struct dict {
    string English, foreign;
} save[1000005];

int i;

bool cmp(dict a, dict b) {
    return a.foreign < b.foreign;
}

string Bsearch(string q) {
    int l = 0, r = i;

    while (l <= r) {
        int mid = l + (r - l) / 2;

        if (save[mid].foreign < q) {
            l = mid + 1;
        }

        else if (save[mid].foreign > q) {
            r = mid - 1;
        }

        else {
            return save[mid].English;
        }
    }

    return "eh";
}

int main() {
    string inp;
    i = 0;

    while(getline(cin, inp)) {
        if (inp.empty()) break;

        string tmp;
        for (int j = 0; j < inp.size(); ++j) {
            if (inp[j] == ' ') {
                save[i].English = tmp;
                tmp = "";
            }

            else {
                tmp += inp[j];
            }
        }
        save[i].foreign = tmp;

        ++i;
    }

    sort(save, save + i, cmp);

    string q;
    while (getline(cin, q)) {
        cout << Bsearch(q) << '\n';
    }
}

:::

---

### [ZJ c575 - APCS 2017-0304-4基地台](https://zerojudge.tw/ShowProblem?problemid=c575)

撰寫者：Koying

可以發現到，每個基地台的範圍越大，就越有機會成功。

將範圍當作 $x$，成功與否當作 $y$ 畫成圖可發現此函數具有單調性。

因此我們可以對基地台範圍二分搜，找到一個最小且可成功的範圍。

至於如何檢查合法與否？一個半徑為 $r$ 的基地台，其實就是從起點開始延伸 $2r$，所以我們可以利用一個變數紀錄目前這個基地台的範圍，如果服務點超出了範圍，再新架一個新的基地台，並延伸 $2r$

:::spoiler Code

#define MAXN 100005
#define MAXM 1000005 
int n, m;
int x[MAXN];

void sol() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }
    sort(x, x + n);
    int l = 0, r = x[n - 1], mid = (l + r) / 2;
    while (l < r) {
        mid = (l + r) / 2;
        int now = 0, cnt = 0;
        for (int i = 0; i < n; i++) {
            if (x[i] > now) {
                now = x[i] + mid;
                cnt++;
            }
        }
        if (cnt > m) {
            l = mid + 1;
        }
        else
            r = mid;
    }
    cout << r << endl;
}

:::

---

### [AtCoder - abc146_c](https://atcoder.jp/contests/abc146/tasks/abc146_c)

撰寫者：Eason and 小麥

在 $1$~$10^{9}$ 二分搜出答案$N$

$a \times N + b \times$ ($N$的位數)

:::spoiler Eason
**38、41 行的1000000000LL 和 1LL
是指long long 型態的1000000000 和 1
因為 max 和 min 的兩個參數型態要一樣**

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    long long a, b, x;
    cin >> a >> b >> x;
    int l = 1, r = 1000000000, prev_mid = 0;
    long long prev_cost = 1e10;

    while (l <= r){
        long long mid = (l + r) / 2;
        long long d = log10(mid) + 1;
        long long cost = a * mid + b * d;

        if (l == r){
            if (cost > x and prev_cost > x){
                cout << 0 << '\n';
            }
            else if (cost > x){
                cout << prev_mid << '\n';
            }
            else{
                cout << mid << '\n';
            }
            break;
        }

        if (cost == x){
            cout << mid << '\n';
            break;
        }
        else if (cost < x){
            prev_mid = mid;
            prev_cost = cost;
            l = min(1000000000LL, mid + 1);
        }
        else{
            r = max(1LL, mid - 1);
        }
    }
    return 0;
}

:::

:::spoiler 小麥

#include <bits/stdc++.h>
#define int long long

using namespace std;

int n, m, k;

bool test(int x) {
    int price = n * x + m * ((int) log10(x) + 1);
    return price <= k;
}

int binarySearch(int left, int right) {
    int result = 0;
    for (int i = (right - left) >> 1; i > 0; i >>= 1) {
        while (test(result + i)) {
            result += i;
        }
    }

    return result;
}

void solve() {
    cin >> n >> m >> k;   

    cout << (min((int) 1e9, binarySearch(0, 1e9 + 1))) << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    solve();

    return 0;
}

:::

---

### [Kattis bootstrappingnumber](https://open.kattis.com/problems/bootstrappingnumber)

撰寫者：Jun-an

輸入一個整數 $n$，
找出一個數字 $x$，滿足 $x^x$ = $n$。

這裡利用二分搜在 $1$ ~ $n$ 之間找出 $x$，
浮點數的誤差值在 $1e$-$6$ 以內。

輸出的時候建議使用 `fix << precision(7) << x`

:::spoiler 參考程式碼

#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

void Bsearch(double n) {
    double l = 0, r = n;

    for (int i = 0; i < 101; ++i) {
        double mid = l + (r - l) / 2;

        if (pow(mid, mid) < n) {
            l = mid;
        }

        else {
            r = mid;
        }
    }

    cout << fixed << setprecision(10) << l + (r - l) / 2 << '\n';
}

int main() {
    double n;
    cin >> n;

    Bsearch(n);
}

:::

---

### [TOJ 55](https://toj.tfcis.org/oj/pro/55/)

撰寫者：Eason

先排序！！

$N$的出現次數 = 第一個大於$N$的索引值 - 第一個大於等於$N$的索引值
這兩個都可以用二分搜求出來
如上圖
左箭頭的索引值為 2
右箭頭的索引值為 5
則 5 的出現次數即為 5 - 2 = 3
<font color=red>但還有一個小問題</font>
如果我要找 16 呢？
:::spoiler Answer
其實就只要在陣列最後面加入一個無限大的數字就好
:::

:::spoiler code

#include<iostream>
#include<algorithm>
using namespace std;

long long arr[1000005];
int n;

int up_bound(long long tar){ // first > tar
    int l = 0, r = n, ind;
    while (l <= r){
        int mid = (l + r) / 2;
        if (l == r){
            ind = mid;
            break;
        }
        if (tar >= arr[mid]){
            l = mid + 1;
        }
        else{
            r = mid;
        }
    }
    return ind;
}

int lw_bound(long long tar){ // first >= tar
    int l = 0, r = n, ind;
    while (l <= r){
        int mid = (l + r) / 2;
        if (l == r){
            ind = mid;
            break;
        }
        if (tar > arr[mid]){
            l = mid + 1;
        }
        else{
            r = mid;
        }
    }
    return ind;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> arr[i];
    }
    arr[n] = 1000000000; // 創造一個無限大的數字放在陣列最後面
    sort (arr, arr + n);
    int q;
    cin >> q;
    for (int i = 0; i < q; i++){
        long long temp;
        cin >> temp;
        int tail = up_bound(temp);
        int head = lw_bound(temp);
        cout << tail - head << '\n';
    }
    return 0;
}

:::
:::spoiler 黑魔法
C++ algorithm標頭檔中有 upper_bound 和 lower_bound 就類似於上面 code 中 up_bound 和 lw_bound

#include<iostream>
#include<algorithm>
using namespace std;

long long arr[1000005];

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
        int n;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> arr[i];
    }
    sort (arr, arr + n);
    int q;
    cin >> q;
    for (int i = 0; i < q; i++){
        long long temp;
        cin >> temp;
        long long *tail = upper_bound(arr, arr + n, temp);
        long long *head = lower_bound(arr, arr + n, temp);
        cout << tail - head << '\n';
    }
    return 0;
}

:::