Algorithm111-2

• Algorithm111-2
  • Divide and Conquer
    • 1_1_Merge_Sort
    • 1_2_Maximum_Subarray
    • 1_3_Dropping_Balls
    • 1_4_The_Stern-Brocot_Number_System
  • Greedy Method
    • 2_1_Greedy_Activity_Selector
    • 2_2_Fractional_knapsack_problem
    • 2_3_Kruskal’s_Algorithm
    • 2_4_The_Bus_Driver_Problem
  • Dynamic Programming
    • 3_1_Rod_cutting
    • 3_2_Longest_common_subsequence
    • 3_3_0-1_knapsack_problem
  • Dynamic Programming
    • 4_1 搜尋迷宮路徑
    • 4_2_Graph_Coloring
    • 4_3_The_Hamming_Distance_Problem
  • Graph
    • 5_1_0/1_knapsack_problem_depth-first_search
    • 5_2_0/1_knapsack_problem_best-first_search
  • Binary Search
    • Longest Increasing Subsequence
    • Minimum Size Subarray Sum
    • Snowman
    • HunterXHunter

Divide and Conquer

1_1_Merge_Sort

題目說明

使用 merge sort 排序法進行排序。
※ merge sort:

-過程：

-範例：

分割主陣列，產生子陣列，再從子陣列中掃描最小元素，填回主陣列。

提醒

1.輸入最多五萬個數
2.變數都是int
3.請善用<limits.h>內的INT_MAX，來當作∞ 。
4.malloc記得free。
5.用O(n²)的演算法會爆炸，可以用Bubble Sort來嘗試看看。

輸入說明

未經排序的數字，數字間以一個空白區隔，最後會有EOF。

輸出說明

輸出為使用 merge sort 排序過的序列，數字間以一個空白區隔（最後一個數字後也有空白），結尾需加上換行符號\n。

程式碼參考

int a[50505];
void merge(int l, int r) {
    int m = (l + r) >> 1;
    int* la = (int*)malloc(sizeof(int) * (r - m + 2)), * lb = (int*)malloc(sizeof(int) * (m - l + 2));
    for (int i = l;i <= m;i++)la[i - l] = a[i];
    for (int i = m + 1;i <= r;i++)lb[i - m - 1] = a[i];
    la[m + 1 - l] = INT_MAX;
    lb[r - m] = INT_MAX;
    int idxl = 0, idxr = 0;
    for (int i = l;i <= r;i++) {
        if (la[idxl] <= lb[idxr]) {
            a[i] = la[idxl];
            idxl++;
        }
        else {
            a[i] = lb[idxr];
            idxr++;
        }
    }
    free(la), free(lb);
    return;
}
void merge_sort(int l, int r) {
    if (l < r) {
        int mid = (l + r) >> 1;
        merge_sort(l, mid);
        merge_sort(mid + 1, r);
        merge(l, r);
    }
    return;
}
int main() {
    int n = 0;
    while (cin >> a[n]) n++;
    n--;
    merge_sort(0, n);
    for (int i = 0;i <= n;i++) {
        cout << a[i] << " ";
    }
    cout << "\n";
    return 0;
}

1_2_Maximum_Subarray

題目說明

使用Divide and conquer找出總和最大的子陣列。

虛擬程式碼

提醒

1.輸入最多五萬個數
2.變數都是int
3.請善用<limits.h>內的INT_MIN，來當作-∞ 。

輸入說明

未經排序的數字，數字間以一個空白區隔，最後會有EOF。

輸出說明

最大總和，需要加上換行符號\n。

程式碼參考

int a[50505];
int main() {
    int n = 0;
    while (cin >> a[n]) n++;
    ll total = 0, ans = INT_MIN;
    for (int i = 0;i < n;i++) {
        total += a[i];
        ans = max(ans, total);
        if (total < 0) total = 0;
        // 如果最大值為負，則必為其中之一元素
        // 若有其中一元素大於等於0，ans必大於等於0
    }
    cout << ans << "\n";
    return 0;
}

1_3_Dropping_Balls

題目說明

uva 679

程式碼參考

int main() {
    FASTER;
    int n;
    while (cin >> n) {
        if (n == -1) break;
        for (int i = 0;i < n;i++) {
            int D, I;
            cin >> D >> I;
            int loc = 1;
            for (int j = 1;j < D;j++) {
                if (I % 2 == 0) { // right
                    loc = loc * 2 + 1;
                    I >>= 1;
                }
                else { // left
                    loc *= 2;
                    I = (I + 1) >> 1;
                }
            }
            cout << loc << "\n";
        }
    }
    return 0;
}

1_4_The_Stern-Brocot_Number_System

題目說明

uva 10077

程式碼參考

int n, m;
void sol(int l_x, int l_y, int r_x, int r_y) {
    int nx = l_x + r_x, ny = l_y + r_y; // now_value
    // cout << nx << " " << ny << "\n";
    if (nx == n && ny == m) {
        cout << "\n"; return;
    }
    else if (nx * m < n * ny) { // To right (bigger)
        cout << "R"; sol(nx, ny, r_x, r_y);
    } // update new left
    else { // To left (smaller)
        cout << "L"; sol(l_x, l_y, nx, ny);
    } // update new right
}
int main() {
    while (cin >> n >> m) {
        if (n == 1 && m == 1) break;
        sol(0, 1, 1, 0);
    }
    return 0;
}

Greedy Method

2_1_Greedy_Activity_Selector

題目說明

問題敘述
使用貪婪演算法，參加最多的活動。

提醒
1.變數都是int。
2.隱藏測資有三萬筆輸入。

輸入說明
序號、開始時間、結束時間，結束時間已排序。

輸出說明
參加的活動序號 + 空白，由小到大排列，結尾有\n。

程式碼參考

int main() {
    int idx, s, f, now = 0;
    while (cin >> idx >> s >> f) {
        if (now <= s) {
            now = f;
            cout << idx << " ";
        }
    }
    cout << "\n";
    return 0;
}

2_2_Fractional_knapsack_problem

題目說明

問題敘述
使用貪婪演算法，拿取價值總和最高的物品（可以分割物品）。

提醒
1.請先依據(價值/重量)排序物品。 2.隱藏測資最多四萬筆。 3.浮點數計算請使用double型態。 4.請使用O(nlgn)的排序演算法，qsort<stdlib.h>。 5.使用%lf,來做輸出。

輸入說明
第一行為背包容量，之後每行都是物品價值、重量。

輸出說明
可賣出的最高價錢，輸出小數點六位數，結尾有換行符號。

程式碼參考

struct objs {
    double v, w;
    double p;
}obj[40005];
int cmp(const void* a, const void* b) {
    const objs* x = (const objs*)a;
    const objs* y = (const objs*)b;
    if (x->p < y->p)return 1;
    else if (x->p > y->p)return -1;
    return 0;
}
int main() {
    int C; cin >> C;
    int n = 0;
    while (cin >> obj[n].v >> obj[n].w) n++;
    for (int i = 0;i < n;i++) { obj[i].p = obj[i].v / obj[i].w; }
    qsort(obj, n, sizeof(objs), cmp);
    double ans = 0;
    for (int i = 0;i < n;i++) {
        if (C >= obj[i].w) {
            C -= obj[i].w;
            ans += obj[i].v;
        }
        else {
            ans += obj[i].p * C;
            C = 0;
        }
        if (C == 0)break;
    }
    printf("%.6lf\n", ans);
    return 0;
}

2_3_Kruskal’s_Algorithm

題目說明

問題描述：
輸入一圖形資料，圖形可由邊集合來描述，每對頂點代表兩頂點之間有邊相連，且每個邊都有其權重，
使用 Adjacency list 儲存圖形資料，利用 Kruskal’s Algorithm 找出 minimum spanning tree。

※ Kruskal’s Algorithm：使用 greedy method 找出 minimum spanning tree。
1) 使用 greedy method 的限制：
a) 所選擇的邊成本總和為最小成本。
b) 只能使用圖形內的邊。
c) 只能使用恰好 n-1 邊。
d) 不可使用會形成迴路的邊。
2) 作法：
a) 根據各邊的成本，將所有邊由小到大排序，每個點各自為一個集合。
b) 由最小的邊開始尋找 minimum spanning tree。
c) 將邊由小到大開始，使用 union - find 將點加入集合，並檢查是否會形成迴路，有以下 2 種情形：
case1. 若與 minimum spanning tree 相連的點集合形成迴路，則不加入此點集合中。
case2. 若未形成迴路，則加入與此點相連之 minimum spanning tree 點集合中。
d) 重複步驟 c ，直到檢查完所有邊，且 minimum spanning tree 的邊個數恰好為 n-1 個。
3) 使用 union - find 檢查迴路：
a) 方法：有下列兩種情形
case1. 若加入一個邊 形成迴路，則頂點 u 和頂點 v 會在同一個點集合中，
即 find( u ) = find( v )。
case2. 若加入一個邊 不會形成迴路，則執行 union( find( u ), find( v ) )。
4) 範例：
將邊由小到大排序 <0,5> <2,3> <1,6> <1,2> <3,6> <3,4> <4,6> <4,5> <0,1>
提醒
1.隱藏測資最多四萬筆。
2.如權重相同優先輸出序號小的數。
3.請使用O(nlogn)的排序演算法來排序。

輸入說明：
輸入一串數字(數字用 tab 隔開，每對數字用換行區格)，
前兩個數字代表與邊相連之兩個頂點，第三個數字代表此邊之權重，且每對 <> 間有空白。
Ex:
0 1 28
0 5 10
1 2 16
1 6 14
2 3 12
3 4 22
3 6 18
4 5 25
4 6 24

輸出說明：
輸出 Adjacency list ，數字與 -> 間及 -> 與 end 間有空白，且每個字皆與 ':' 之間有空白，
再依找尋順序並標出順序，輸出所找出 minimum spanning tree 的所有邊及其最小成本。

程式碼參考

vector<pair<int, pair<int, int>>>edge;
vector<int>id, sz;
int  n;
int root(int i) {
    while (i != id[i]) {
        id[i] = id[id[i]];
        i = id[i];
    }
    return i;
}
bool Find(int p, int q) {
    return root(p) == root(q);
}
void Union(int p, int q) {
    int u = root(p);
    int v = root(q);
    if (sz[u] < sz[v]) {
        id[u] = v;
        sz[v] += sz[u];
    }
    else {
        id[v] = u;
        sz[u] += sz[v];
    }
}
void solve() {
    for (int i = 0; i < n; ++i) {
        id.PB(i);
        sz.PB(1);
    }
    int len = edge.size(), e = 0, cost = 0;
    for (int i = 0;i < len;i++) {
        int u = edge[i].second.first;
        int v = edge[i].second.second;
        if (!Find(u, v)) {
            Union(u, v);
            cout << ++e << ": <" << u << "," << v << ">\n";
            cost += edge[i].first;
        }
    }
    cout << "\n" << "The cost of minimum spanning tree: " << cost << "\n";
}
int main() {
    vector<int>adj[40005];
    int u, v, w;
    while (cin >> u >> v >> w) {
        adj[u].PB(v);
        adj[v].PB(u);
        n = max({ n,u,v });
        edge.PB({ w,{u,v} });
    }
    n++;
    cout << "Adjacency list:\n";
    for (int i = 0;i < n;i++) {
        int len = adj[i].size();
        if (len > 0) {
            cout << i << ": ";
            for (int j : adj[i]) {
                cout << j << " -> ";
            }
            cout << "end\n";
        }
    }
    cout << "\n";
    sort(edge.begin(), edge.end());
    cout << "minimum spanning tree:\n";
    solve();
    return 0;
}

2_4_The_Bus_Driver_Problem

題目說明

uva 11389

盡量配滿每位司機的路線長度上限，就能得到最小花費。這裡使用的策略是讓早上最短的路線搭配傍晚最長的路線分配給每一位司機。

提醒
1.輸出結尾有換行符號。 2.隱藏測資有一萬組輸入。

程式碼參考

int a[111], b[111];
bool cmp(int x, int y) {
    return x > y;
}
int main() {
    int n, d, r;
    while (cin >> n >> d >> r) {
        if (n == 0 && d == 0 && r == 0)break;
        for (int i = 0;i < n;i++) { cin >> a[i]; }
        for (int i = 0;i < n;i++) { cin >> b[i]; }
        sort(a, a + n);
        sort(b, b + n, cmp);
        int ans = 0;
        for (int i = 0;i < n;i++) {
            if (a[i] + b[i] > d) {
                ans += r * (a[i] + b[i] - d);
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

Dynamic Programming

3_1_Rod_cutting

題目說明

問題敘述：
不同長度的竿子可賣的價格不同，假設有一條竿子，不限切成幾分，請使用動態規劃法，找出能賣的最高價格。

輸入說明：
第一行輸入，竿子的長度(1 至 50000)，
第二行之後，輸入每種長度的賣價（如下表範例），長度、賣價以空格分開，
最後一行輸入0 0，代表輸入結束。
Ex:
4
1 1
2 5
…
9 24
10 30
0 0

輸出說明：
可賣的最高價格，結尾需加上換行符號\n。

程式碼參考

ll dp[55555], L;
int main() {
    cin >> L;
    ll len, price;
    while (cin >> len >> price) {
        if (len == 0 && price == 0)break;
        dp[len] = price;
    }
    for (ll i = 1;i <= L;i++) {
        for (ll j = 1;j < i;j++) {
            dp[i] = max(dp[i], dp[i - j] + dp[j]);
        }
        // cout << i << ": " << dp[i] << "\n";
    }
    cout << dp[L] << "\n";
    return 0;
}

3_2_Longest_common_subsequence

題目說明

問題敘述：
一個子序列是原本序列的一部分，請找出兩個序列的最長共同子序列，並算出最長共同子序列的長度。

For example:
X = 〈A, B, C, B, D, A, B〉
Y = 〈B, D, C, A, B, A〉
〈B, C, A〉is a common subsequence of both X and Y.
〈B, C, B, A〉is an longest common subsequence (LCS) of X and Y.
長度 = 4

輸入說明：
輸入兩個任意長度的字串，內容由英文大小寫字母和數字組成（長度1 至 20000）。
例：
UABCDDEA
CACCEA
輸出說明：
最長共同子序列的長度，結尾需加上換行符號\n。

*提示：i 用 i%2 取代，i-1 用 (i+1)%2 取代。

程式碼參考

short dp[20202][20202] = { 0 };
int main() {
    FASTER;
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    int sz1 = s1.size(), sz2 = s2.size();
    for (int i = 1; i <= sz1; i++) {
        for (int j = 1; j <= sz2; j++) {
            if (s1[i - 1] == s2[j - 1])dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    cout << dp[sz1][sz2] << "\n";
    return 0;
}

3_3_0-1_knapsack_problem

題目說明

問題敘述：
使用動態規劃法 解 0-1背包問題（0/1 Knapsack Problem），
每個物品都有特定的重量與價值，且每個物品皆不可切割和重複拿取，
請在背包的耐重度範圍內把物品放入背包，找到背包內物品總和可達到的最高價值和物品的拿法。

輸入說明：
第一行輸入，背包大小（耐重。最大可能到200），
第二行之後，輸入物品代號、重量、價值，以空格分開，
(物品最多可能到 8000 筆)，
最後一行輸入-1 -1 -1，代表輸入結束。

輸出說明：
第一行，達到最高價值的情況下，背包內的物品代號，每個代號後都有一個空格。
第二行，可達到的最高價值，結尾需加上換行符號\n。

程式碼參考

struct Item {
    int id, g, v;
}item[8888];
ll dp[8888][222];
bool carry[8888][222];
int main() {
    FASTER;
    int w; cin >> w;
    int n = 0;
    while (cin >> item[n].id >> item[n].g >> item[n].v) {
        if (item[n].id == -1 && item[n].g == -1 && item[n].v == -1)break;
        n++;
    }
    for (int i = 0;i <= n;i++) {
        for (int j = 0;j <= w;j++) {
            if (j - item[i].g >= 0 && dp[i][j - item[i].g] + item[i].v > dp[i][j]) {
                dp[i + 1][j] = dp[i][j - item[i].g] + item[i].v;
                carry[i][j] = 1;
            }
            else { dp[i + 1][j] = dp[i][j]; }
        }
    }
    for (int i = n, j = w;i >= 0;i--) {
        if (carry[i][j] == 1) {
            cout << item[i].id << " ";
            j -= item[i].g;
        }
    }
    cout << "\n";
    cout << dp[n][w] << "\n";
    return 0;
}

Dynamic Programming

4_1 搜尋迷宮路徑

題目說明

問題描述：
給定一個迷宮，並定義路口及出口，
請撰寫一程式輸出從入口到出口的最短路徑。

※ 迷宮的表示方法：
下圖為一個給定的 5*5 迷宮，且入口為 (1, 1)，出口為 (5, 5)。
我們將以一個二維陣列 maze[row][col] 來表示此迷宮，
其中，row 代表列數， col 代表行數；
0 代表可通行的路徑，1 代表有障礙不可通行之路徑。
Ex：maze[1][1] = 0，maze[1][4] = 1。

※ 作法：

使用breadth-first 來搜尋路徑並以 backtracking 找到最短的路徑。

breadth-first example：

輸入說明：
輸入為一個迷宮，以多列表示。
第一列有六個數字，並以 空格 隔開，
內容分別為：迷宮的大小(列數Y與行數X) 起點的座標(Y,X) 終點的座標(Y,X)
Ex：5 5 1 1 5 5，表示迷宮的大小為 5*5，座標 (1,1) 為起點，(5,5) 為終點。
第二列之後即為迷宮，0 表示可通行路徑，1 表示有障礙不可通行。

輸出說明：
依照問題描述中「作法」的敘述，找出迷宮中能夠到達終點的路徑，並將最短路徑印出，
第一為 最短路徑長度，
之後的每列 印出路徑中每一個走過的座標，並以換行隔開，
最後一列有換行符號。
Ex：
最短路徑長度
(path1 座標)
(path1 座標)
…

提示：檢查順序為上方開始順時鐘方向

程式碼參考

const int w[8][2] = { {-1, 0}, {-1, 1} ,{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0,-1}, {-1, -1} };
int n, m, sx, sy, tx, ty;
int maze[505][505];
map<pair<int, int>, pair<int, int>>pre;
vector<pair<int, int>>path;
void back_track(int x, int y) {
    if (!(x == sx && y == sy)) back_track(pre[{x, y}].first, pre[{x, y}].second);
    path.PB({ x,y });
    return;
}
void solve() {
    cin >> n >> m >> sx >> sy >> tx >> ty;
    for (int i = 0;i <= n + 1;i++) {
        maze[i][0] = 1;
        maze[i][m + 1] = 1;
    }for (int j = 0;j <= m + 1;j++) {
        maze[0][j] = 1;
        maze[n + 1][j] = 1;
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            char c; cin >> c;
            if (c == '0')maze[i][j] = 0;
            else maze[i][j] = 1;
        }
    }
    
    queue<pair<int, int>> q;
    q.push({ sx,sy });
    while (!q.empty()) {
        int nx = q.front().first, ny = q.front().second;
        q.pop();
        if (nx == tx && ny == ty) {
            back_track(tx, ty);
            int sz = path.size();
            cout << sz << "\n";
            for (auto i : path)cout << "(" << i.first << "," << i.second << ")" << "\n";
            return;
        }
        for (int i = 0; i < 8; i++) {
            int dx = nx + w[i][0], dy = ny + w[i][1];
            if (!maze[dx][dy] && pre.find({ dx,dy }) == pre.end()) {
                pre[{dx, dy}] = { nx, ny };
                q.push({ dx, dy });
            }
        }
    }
    return;
}

4_2_Graph_Coloring

題目說明

uva 193

程式碼參考

vector<int>edge[333];
vector<int> ans, now;
bool color[333];
int n, k;
void dfs(int x) {
    if (x > n) {
        if (now.size() > ans.size())ans = now;
        return;
    }
    bool f = 1;
    for (int i : edge[x]) {
        if (color[i] == 1) {
            f = 0;
            break;
        }
    }
    if (f) {
        color[x] = 1;
        now.PB(x);
        dfs(x + 1);
        now.pop_back();
    }
    color[x] = 0;
    dfs(x + 1);
}
int main() {
    FASTER;
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> k;
        mem(color, 0);
        now.clear(), ans.clear();
        for (int i = 1;i <= n;i++)edge[i].clear();
        for (int i = 0;i < k;i++) {
            int u, v;
            cin >> u >> v;
            edge[u].PB(v);
            edge[v].PB(u);
        }
        dfs(1);
        cout << ans.size() << "\n";
        for (int i = 0;i < ans.size();i++)
            cout << ans[i] << " \n"[i == ans.size() - 1];
    }
    return 0;
}

4_3_The_Hamming_Distance_Problem

題目說明

uva 729

程式碼參考

void solve(int n, int h, string s, int c) {
    if (n == s.size()) {
        if (h == c)cout << s << "\n";
        return;
    }
    if (c <= h)solve(n, h, s + '0', c);
    solve(n, h, s + '1', c + 1);
}
int main() {
    FASTER;
    int t;
    cin >> t;
    while (t--) {
        int n, h;
        cin >> n >> h;
        solve(n, h, "", 0);
        if (t)cout << "\n";
    }
    return 0;
}

Graph

5_1_0/1_knapsack_problem_depth-first_search

題目說明

使用 depth-first search 解 0-1背包問題（0/1 Knapsack Problem），
每個物品都有特定的重量與價值，且每個物品皆不可切割和重複拿取，
請在背包的耐重度範圍內把物品放入背包，找到背包內物品總和可達到的最高價值和物品的拿法。

depth-first-search example:

程式碼參考

// TLE，抱歉我不會QQ

5_2_0/1_knapsack_problem_best-first_search

題目說明

使用 best-first_search 解 0-1背包問題（0/1 Knapsack Problem），
每個物品都有特定的重量與價值，且每個物品皆不可切割和重複拿取，
請在背包的耐重度範圍內把物品放入背包，找到背包內物品總和可達到的最高價值和物品的拿法。

best-first_search example:

程式碼參考

struct Item {
    int id;ll w, v;
    float vpw;
    Item(int _id, ll _w, ll _v) {
        id = _id, w = _w, v = _v;
        vpw = v * 1.0 / w;
    }
};
vector<Item>item;
void merge(int l, int m, int r) {
    Item* la = (Item*)malloc(sizeof(Item) * (r - m + 2)), * lb = (Item*)malloc(sizeof(Item) * (m - l + 2));
    for (int i = l;i <= m;i++)la[i - l] = item[i];
    for (int i = m + 1;i <= r;i++)lb[i - m - 1] = item[i];
    la[m - l + 1] = (Item(-1, INT_MAX, 0));
    lb[r - m] = (Item(-1, INT_MAX, 0));
    int idxl = 0, idxr = 0;
    for (int i = l;i <= r;i++) {
        if (la[idxl].vpw > lb[idxr].vpw) {
            item[i] = la[idxl];
            idxl++;
        }
        else {
            item[i] = lb[idxr];
            idxr++;
        }
    }
    return;
}
void merge_sort(int l, int r) {
    if (l < r) {
        int mid = (l + r) >> 1;
        merge_sort(l, mid);
        merge_sort(mid + 1, r);
        merge(l, mid, r);
    }
    return;
}
ll W;
int n;
ll predict(ll id, ll w, ll v) {
    ll ww = w;
    ll vv = v;
    for (int i = id;i <= n;i++) {
        ww += item[i].w;
        if (ww > W) {
            ww -= item[i].w;
            vv += (W - ww) * item[i].vpw;
            break;
        }
        else {
            vv += item[id].v;
            if (ww == W)break;
        }
    }
    return vv;
}
ll ans = 0;
string store;
struct PQ {
    ll  v, w;
    int id;bool f;
    string s;
    PQ(ll _v, ll _w, int _id, bool _f, string _s) {
        v = _v;w = _w;id = _id;f = _f;
        s = _s;
    }
    bool operator < (PQ other)const {
        return 0;
    }
};

void bfs() {
    ll w = 0, v = 0;
    ll vv;string s = "";
    priority_queue<pair<ll, PQ>>pq;
    vv = predict(0, w, v);
    pq.push({ vv,PQ(v, w, 0, 1, s) });
    vv = predict(1, w, v);
    pq.push({ vv,PQ(v, w, 0, 0, s) });
    while (!pq.empty()) {
        v = pq.top().second.v;
        w = pq.top().second.w;
        vv = pq.top().first;
        int id = pq.top().second.id;
        bool f = pq.top().second.f;
        s = pq.top().second.s;
        pq.pop();
        if (vv <= ans)continue;
        if (f) {
            w += item[id].w;
            if (w > W)continue;
            s += to_string(item[id].id);
            s.push_back(' ');
            v += item[id].v;
            if (v > ans) {
                ans = v;
                store = s;
            }
        }
        pq.push({ vv,PQ(v, w, id + 1, 1, s) });
        vv = predict(id + 2, w, v);
        pq.push({ vv,PQ(v, w, id + 1, 0, s) });
    }
}
int main() {
    FASTER;
    cin >> W;
    ll id, w, v;
    n = 0;
    while (cin >> id >> w >> v) {
        if (id == -1 && w == -1 && v == -1) break;
        item.push_back(Item(id, w, v));
    }
    n = item.size() - 1;
    merge_sort(0, n); // sort(item.begin(), item.end(), cmp);
    bfs();
    cout << store << "\n";
    cout << ans << "\n";
    return 0;
}

Binary Search

Longest Increasing Subsequence

題目說明

給定一個未排序的整數陣列，請算出最長遞增序列的長度。例如：輸入整數陣列 [10, 9, 2, 5, 3, 7, 101, 18]，則最長遞增序列為 [2, 3, 7, 101]。請設計一個 O(nlogn) 的演算法解決這個問題。

輸入說明

第一個整數 n 代表整數陣列的長度。接著有 n 個整數 a1 , a2 , … , an，代表整數陣列的內容。

• 1 ≤ n ≤ 10⁶
• 1 ≤ a_i ≤ n for all 1 ≤ i ≤ n

輸出說明

請輸出一個整數，代表最長遞增序列的長度。

程式碼參考

int a[MXN];
int b_s(int l, int r, int x) {
    while (l < r) {
        int mid = (l + r) >> 1;
        if (a[mid] >= x)r = mid;
        else l = mid + 1;
    }
    return l;
}
int main() {
    FASTER;
    int T = 1;
    //cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int idx = 1;
        for (int i = 0;i < n;i++) {
            int x;
            cin >> x;
            if (x > a[idx - 1])
                a[idx++] = x;
            else {
                int tem_pos = b_s(0, idx, x);
                a[tem_pos] = min(a[tem_pos], x);
            }
        }
        cout << idx - 1 << "\n";
    }
    return 0;
}

Minimum Size Subarray Sum

題目說明

給定一個未排序的整數陣列和一整數 s，請找出最小的子陣列使其元素總和 ≥ s。例如：輸入整數陣列 [2, 3, 1, 2, 4, 3] 和 s = 7，則 [4, 3] 為最小的子陣列且其元素總和 ≥ 7。

輸入說明

第一個整數 n 代表整數陣列的長度。第二個整數為 s。接著有 n 個整數 a₁ , a₂ , … , a_n，代表整數陣列的內容。

1 ≤ n ≤ 10⁷
​1 ≤ ai ≤ 100 for all 1 ≤ i ≤ n
1 ≤ s ≤ 10⁸

輸出說明

請輸出一個整數，代表最小子陣列的長度。若此子陣列不存在，則輸出 0。

程式碼參考

queue<int>q;
int main() {
    FASTER;
    ll n, s;
    cin >> n >> s;
    ll total = 0, ans = n + 1;
    for (int i = 0;i < n;i++) {
        ll a;cin >> a;
        total += a;
        q.push(a);
        while (total > s) {
            ll sz = q.size();
            ans = min(ans, sz);
            total -= q.front();
            q.pop();
        }
    }
    if (ans == n + 1)ans = 0;
    cout << ans << "\n";
    return 0;
}

Snowman

題目說明

小雪是個好動的小朋友，在這個下雪的季節裡，小雪喜歡天天堆雪人，他發現一件很有趣的事情，假設第 i 天的溫度是 C_i ，而雪人的大小是 X，那麼經過一天後雪人的大小會變成 X - C_i (若小於等於0 代表雪人整個融化不見了)。
在接下來的 n 天裡，小雪每天都會堆一個雪人，但是因她心情而定，雪人的大小都會不盡相同，第 i 天的雪人大小為 X_i ，小雪也是個情感豐富的人，她認為每個她所堆的雪人都是具有獨自的生命力，因此她想知道每個雪人將在第幾天的時候消失，但是每天盯著這些雪人對於小雪來說太過困難了，希望你能夠幫幫她。

輸入說明

第一個整數 n 代表天數。第二行有 n 個整數 X₁ , X₂ , … , X_n，第三行有 n 個整數 C₁ , C₂ , … , C_n。

1 ≤ n ≤ 10⁵
1 ≤ X_i , C_i ≤ 10⁹ , for all 1 ≤ i ≤ n

輸出說明

請輸出 n 個整數，第 k 個數字 d_k 代表雪人將在 第 d_k 天融化掉，如果在給定的 n 天裡都不會融化的話，請輸出 -1

說明投影片

程式碼參考

ll x[111111], c[111111], ans[111111];
int main() {
    FASTER;
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++)cin >> x[i];
    for (int i = 1;i <= n;i++) {
        cin >> c[i];
        c[i] += c[i - 1];
    }
    for (int i = 1;i <= n;i++) {
        int id = (lower_bound(c + i, c + n + 1, x[i] + c[i - 1]) - c);
        if (id == n + 1)id = -1;
        cout << id << " ";
    }
    cout << "\n";
    return 0;
}

HunterXHunter

題目說明

小傑最愛奇犽了。
小傑跟奇犽正在練習影分身術，在一條數線上小傑總共有 n 個分身，奇犽有 m 個分身 ，因為奇犽比小傑還要厲害，所以他影分身的數量一定不比小傑少。
小傑太喜歡奇犽了，即便是分身也要找奇犽玩耍，每個小傑分身在一個時間單位內可以移動 1 的距離，奇犽分身則待在原地不動，當小傑走到奇犽的位置時便可以跟他玩耍，但是奇犽具有獨佔性，每個奇犽只能跟一個小傑玩耍，小傑想要知道，至少要花多少時間才能讓每個小傑分身都能找到人玩耍。

輸入說明

第一行有兩個整數 n , m 。第二行有 n 個整數 x₁ , x₂ , … , x_n，代表小傑分身的位置，第三行有 m 個整數 y₁ , y₂ , … , y_m，代表奇犽分身的位置。

1 ≤ n , m ≤ 10⁵
​0 ≤ x_i , y_j ≤ 10⁹ for all 1 ≤ i ≤ n , 1 ≤ j ≤ m

輸出說明

輸出一個整數，代表最少需要多少時間才能達成。

程式碼參考

const int MXN = 1e5 + 100;
int n, m;
int x[MXN], y[MXN];

bool check(int t) {
    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j < m && !(y[j] >= x[i] - t && y[j] <= x[i] + t)) j++;
        if (j == m) return false;
        // else match ， 表示y[j]能在t時間內走到x[i]
        j++;
        if (m - j < n - i - 1) return false; // 剩下的不夠配對
    }
    return true;
}
int main() {
    FASTER;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> x[i];
    for (int i = 0; i < m; i++) cin >> y[i];
    sort(x, x + n);
    sort(y, y + m);

    int l = 0, r = 1e9;
    while (l < r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    cout << l << "\n";
    return 0;
}