Codeforces 1492C - Maximum width (二元搜尋)

題目大意

有兩個字串 s and t，題目定義一個 beautiful 的概念，beautiful 概念如下
必須 \(s_p_i = t_i\)，且 \(1 \leq p_1 < p_2 < … \leq n\)，一個 beautiful 概念應該是 \(max_{1 \leq i \leq m } (p_{i+1} - p_i\)

請你輸出最大的 beautiful width

題目連結

重點觀念

• 二分搜尋
• 理解英文題目

分析

其實就是按照題目的規則，將 t 字串的字元依照 t 的順序，分布在 s 的字串中，並且讓分布的其中一個距離最大，並且輸出他。

這樣要怎麼思考呢，很簡單，我們可以用二分搜尋來解決此問題。

我們先用一個陣列 \(p\) 表示如果我們都將 t 的字串放在 s 相同字元的最前面，再來我們只要能夠將 \(t_{i+1}\) 字元拉最遠，就可以達到我們的要求。

用 upperbound 讓 \(t_i\) 字串放在 s 相同字元的最前面並記錄在 \(p\)
用 lowerbound 找出 \(t_{i+1}\) 字元拉最遠的位置，在跟 \(t_i\) 相減就能記錄這次的最大長度。

QUESTION: 為甚麼找最前面用 upperbound，找最後面用 lowerbound 呢

• 第一點 upperbound
  那是因為 c++ 的特性，lowerbound 會找到 \(element \geq value\) 的值，如果 value 是剛剛的最左邊，那下個字元如果跟上個字元相同那下次的 lowerbound 也會找到同樣的左邊邊界，但實際必須加一，因此這裡用 upperbound 就沒有等於的情況。
• 第二點 lowerbound
  第二個點為甚麼要用 lowerbound，因為 upperbound 會找到 \(element > value\) 的值，如果值是剛剛的最右邊 那下個字元如果跟上個字元相同那下次的 upperbound，也會找到同樣的右邊邊界，因此這邊改用 lowerbound 並且減一來減少此情況。lowerbound 有等於的情況就不會找到相同邊界，再透過減一表示跟剛剛的邊界不同。

參考連結

Codeforces Round #704 Editorial - ch_egor’s blog
Codeforces-1492 C. Maximum width（构造）- tomjob

心得

這題我原本是想要我的方式來寫，透過字串壓縮來解決此題，但因為比賽時間只有 2hr，我寫前面的題目就來不及了後來就沒有將此題實現，後來看了其他人的寫法後覺得其他人的寫法更讚，因此學習然後寫一遍高手的寫法，讓我學習學習。

確實網路上永遠都會有人寫得比我更好，這種寫法讓我學起來，這樣會讓我學得更快！以後用得更好。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 0x3f3f3f
using namespace std;
string s, t; //放題目的兩個字串
int n, m, pre = -1, nxt = MAXN, num, ans;  
//pre 當前的最左邊邊界，nxt 當前的最右邊邊界
int p[MAXN]; //每一個字元的最右邊邊界
vector<int> vec[30]; //紀錄每個相同字元的 index，方便二分搜尋

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> n >> m; //輸入資料
    cin >> s >> t;

    for(int i = 0; i < n; i++){ //將相同字元放入同樣 vector
        num = s[i] - 'a';
        vec[num].push_back(i);
    }

    for(int i = 0; i < m; i++){ //對每個字元找出最左邊邊界
        num = t[i] - 'a'; 
        p[i] = *upper_bound(vec[num].begin(), vec[num].end(), pre); 
        //找最左邊邊界
        //cout << "pre p[i] " << i << ' ' << p[i] << '\n';
        pre = p[i];
    }
    nxt = n;
    for(int i = m-1; i > 0; i--){
        num = t[i] - 'a';
        p[i] = *--lower_bound(vec[num].begin(), vec[num].end(), nxt); //找最右邊邊界
        nxt = p[i]; //將 p[i] 改為最右邊邊界，方便等等計算
        //cout << "nxt p[i] " << i << ' ' << p[i] << '\n';
        ans = max(ans, p[i] - p[i-1]); //比較哪個比較大
        //i 與 i-1，和 i+1 與 i 相同概念。
    }
    cout << ans << '\n'; //輸出答案
    return 0;
}