---
# System prepended metadata

title: Week 9：單調性與單調佇列
tags: [S3 公開資源]

---

# Week 9：單調性與單調佇列

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

:::info
時間：04/16 9:00 ~ 17:00
地點：成大資工系新館 **65304** 教室
主題：單調性與單調佇列
直播連結：https://youtube.com/live/IJLZFzmlYo8?feature=share
:::

# 必作題題解

[TOC]

## 二章後半


### [CSES 1640 - Sum of Two Values](https://cses.fi/problemset/task/1640/)

撰寫者：Eason

用雙指針去找
複雜度：$O(n)$

:::spoiler code
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#define ll long long
using namespace std;

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    ll n, x;
    cin >> n >> x;
    vector <pair<ll, ll> > v;
    for (int i = 1; i <= n; i++){
        ll temp;
        cin >> temp;
        v.push_back(make_pair(temp, i));
    }
    sort (v.begin(), v.end());
    int l = 0, r = n - 1;
    while (true){
        ll sum = v[l].first + v[r].first;
        if (l == r){
            cout << "IMPOSSIBLE\n";
            break;
        }
        else if (sum == x){
            cout << v[l].second << ' ' << v[r].second << '\n';
            break;
        }
        else if (sum < x) l++;
        else if (sum > x) r--;
    }
    return 0;
}
```
:::

---

### [UVa 138 - Street Numbers](http://domen111.github.io/UVa-Easy-Viewer/?138)

撰寫者：fishhh

這一題網路上查應該都是數學解。分析一下數學解複雜度，對於每個 n 窮舉($O(n)$)，每次驗證是$O(1)$
所以數學解是$O(n)$

如果不用數學解呢?

你會發現，在 k 越大的同時，從 $1+...+k$ 的值會大於 $k+...+n$
在k小於一定值時會小於，在k大於一定值時會大於，這就是他的單調性!
所以我們可以對他二分搜。
所以複雜度會是$O(nlogn)$。 喔不對 這個會TLE QQ

其中我註解掉的的地方是數學解的部分
至於 fd 函數，它的功能是對一個 n 找有沒有可以符合的 k
如果有，就回傳 k 沒有就回傳 0。


:::spoiler 參考程式碼
```cpp=
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

long long int fd(int n){
    long long int now = 0;
    long long int add = (1<<20);
    long long int pre_sum,last_sum;
    while(add){
        if(now+add>n){
            add/=2;
            continue;
        }
        pre_sum = ((now+add+1)*(now+add))/2;
        last_sum = ((n+now+add)*(n-now-add+1))/2;
        if(last_sum>=pre_sum){
            now+=add;
        }
        else{
            add/=2;
        }
    }
    pre_sum = ((now+add+1)*(now+add))/2;
    last_sum = ((n+now+add)*(n-now-add+1))/2;

    if(last_sum==pre_sum){
        return now;
    }
    return 0;
}
int main(){
    long long int houseNumber = 1;
    for( int i = 0 ; i < 10 ; ++i ){
        bool isAnswer = false;
        while( !isAnswer ){
            ++houseNumber;
            long long int ret = fd(houseNumber);
            if(ret){
                printf("%10.0d%10.0d\n", ret, houseNumber);
                isAnswer = 1;
            }
            // double lastNumber = (-1 + sqrt(1.0 + houseNumber * houseNumber * 8)) / 2;
            // if( lastNumber == floor(lastNumber) ){
            // printf("%10.0lf%10.0lf\n", houseNumber, lastNumber);
            // isAnswer = true;
            // }
        }
    }
    return 0;
}
```
:::

這裡改成 sliding window 的作法。




---

### [CSES 1660 - Subarray Sums I](https://cses.fi/problemset/task/1660)

撰寫者：Eason

題目要求區間 $[l, r]$ 的和要等於 $x$

枚舉左界，在左界固定的情況二分搜右界

若要用前綴和求區間 $[l, r]$ 的和
=> $prefix[r] - prefix[l - 1]$

:::spoiler code
```cpp=
#include<bits/stdc++.h>
#define ll long long
#define weakson ios::sync_with_stdio(0), cin.tie(0);
using namespace std;

ll arr[200005], prefix[200005];
int n, x;

int bin_search(int lp){
    // 左界為 lp
    // 在利用二分搜求出右界
    int l = lp, r = n + 1;
    // 這邊的 l, r 並不是左、右界
    // 而是用來二分搜右界的變數
    while (l + 1 <= r){
        int mid = (l + r) / 2;
        ll sum = prefix[mid] - prefix[lp];
        if (sum == x){
            return 1;
        }
        else if (sum > x){
            r = mid;
        }
        else{
            l = mid + 1;
        }
    }
    return 0;
}

int main(){
    weakson;
    cin >> n >> x;
    prefix[0] = 0;
    for (int i = 0; i < n; i++){
        cin >> arr[i];
        prefix[i + 1] = prefix[i] + arr[i];
    }
    int ans = 0;
    for (int i = 0; i < n; i++){ // 枚舉左界
        ans += bin_search (i);
    }
    cout << ans << '\n';
    return 0;
}
```
:::

---

### [ZJ g277 - 幸運數字](https://zerojudge.tw/ShowProblem?problemid=g277)

撰寫者：$Jun$-$an$

這題要在 $[$ $L$ $,$ $R$ $]$ 區間之中找到最小值的位置 $m$
接著將區間分為 $[$ $L$ $,$ $m$ $-$ $1$ $]$ 跟 $[$ $m$ $+$ $1$ $,$ $R$ $]$ 並分別計算出區間總和
區間總和最大的那個即為幸運數字所在的區間
繼續上述步驟直到 $L$ $==$ $R$。

這裡使用前綴和處理區間總合的問題，總和可能會超過 $int$ 範圍，所以要使用 $long$ $long$ 儲存

區間之中的最小值位置 $m$ 則是使用 $pair$ 將數字跟索引值綁在一起由大到小排序，每次查詢時判斷索引值是否在 $L$ ~ $R$ 之間，如果不是就刪掉，重複直到找到符合的。

需要使用 $I/O$ 優化

:::spoiler 程式碼
```cpp=
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>

#define weak ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;

int nums[300005] = {0};
long long prefix_sum[300005] = {0};
vector<pair<int, int>> save;

bool cmp(pair<int, int> l, pair<int, int> r) {
    return l.first > r.first;
}

int find_min(int L, int R) {
    while (true) {
        pair<int, int> tmp = save.back();

        if (L - 1 <= tmp.second && tmp.second <= R - 1) {
            save.pop_back();

            return tmp.second;
        }

        else {
            save.pop_back();
        }
    }
}

int main() {
    weak

    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
        save.push_back(make_pair(nums[i], i));
    }
    sort(save.begin(), save.end(), cmp);

    for (int i = 1; i <= n; ++i) {
        prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1];
    }

    int L = 1, R = n;
    while (L < R) {
        int mn_idx = find_min(L, R) + 1;

        if (prefix_sum[mn_idx - 1] - prefix_sum[L - 1] < prefix_sum[R] - prefix_sum[mn_idx]) {
            L = mn_idx + 1;
        }

        else {
            R = mn_idx - 1;
        }
    }

    cout << nums[R - 1] << '\n';

    return 0;
}
```
:::

---

### [ZJ h084 - 牆上海報](https://zerojudge.tw/ShowProblem?problemid=h084)

撰寫者：fishhh

先發現一件事，在 $x$ 由小到大，那麼可以放完這件事成功與否就會類似下面這樣。
x = 1 2 3 4 5
ok= 1 1 1 0 0...
也就是說會有一段 1 再來全部都是 0 所以我們就是要找那個最大的 1 出現的位置。

至於貪心的部分就去看講義有詳細的說明。

:::spoiler
```cpp=
#include "iostream"
using namespace std;
int ary[200010]={},flag[6010]={};
int n,k;
bool test(int x){
    int cont = 0,i,j;
    for(i=1,j=1;i<=n&&j<=k;i++){
        if(ary[i]>=x)cont++;
        else{
            cont = 0;
        }
        if(cont==flag[j]){
            cont = 0;
            j++;
        }
    }
    if(j==k+1){
        return 1;
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>ary[i];
    for(int i=1;i<=k;i++)cin>>flag[i];
    
    int now = 0;
    int add = (1<<28);
    
    while(add){
        if(!test(now+add)){
            add/=2;
        }
        else{
            now+=add;
        }
    }

    cout<<now<<"\n";
}
```
:::




---

### [CSES 1084 - Apartments](https://cses.fi/problemset/task/1084/)

撰寫者：Eason

兩組序列排序後利用雙指針就可以了
（一個指向 applicants 一個指向 apartments）

需要考慮三個情況
1. 公寓剛好符合
2. 公寓太小
3. 公寓太大

- 如果對第 $i$ 人公寓太大，對 $i+1$ 人不一定太大
- 如果對第 $i$ 人公寓太小，下一個公寓可能剛好符合他的需求

複雜度：$O(max(n, m))$

:::spoiler code
```cpp=
#include<bits/stdc++.h>
#define weakson ios::sync_with_stdio(0), cin.tie(0);
using namespace std;

int main(){
    int n, m, k;
    cin >> n >> m >> k;
    int a[200005], b[200005];
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    for (int i = 0; i < m; i++){
        cin >> b[i];
    }
    sort (a, a + n);
    sort (b, b + m);
    int ap = 0, bp = 0, ans = 0;
    while (ap < n && bp < m){
        if (abs (a[ap] - b[bp]) <= k){ // 剛好符合
            ap++;
            bp++;
            ans++;
        }
        else if (b[bp] > a[ap] + k){ // 公寓太大
            ap++;
        }
        else if (b[bp] < a[ap] - k){ // 公寓太小
            bp++;
        }
    }
    cout << ans << '\n';
    return 0;
}
```
:::

---

### [CSES 1641 - Sum of Three Values](https://cses.fi/problemset/task/1641/)

撰寫者：$Jun$-$an$

給定一個數列，找出三個數字總和為 $target$，回傳這三個數的索引值。

使用 $pair$ 將數字與索引值綁在一起後由小到大排序
接著掃過每個數字，同時用 $two$ $pointer$ 的概念
判斷當前數字 $n$ $+$ $save[L]$ + $save[R]$ 是否等於 $target$
可以知道 $save$ 是排序過的數列，
如果 $<target$ ，$L+1$
否則，$R-1$

:::spoiler 程式碼
```cpp=
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>

using namespace std;

int nums[5005] = {0};
vector<pair<int, int>> save;

int main() {
    int n, target;
    cin >> n >> target;

    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
        save.push_back(make_pair(nums[i], i + 1));
    }

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

    bool flag = false;
    for (int i = 0; i < n; ++i) {
        int L = 0, R = n - 1;
        while (L < R) {
            if (L == i) {
                ++L;
            }

            else if (R == i) {
                --R;
            }

            else {
                if (save[i].first + save[L].first + save[R].first < target) {
                    ++L;
                }

                else if (save[i].first + save[L].first + save[R].first > target) {
                    --R;
                }

                else {
                    cout << save[i].second << ' ' << save[L].second << ' ' << save[R].second << '\n';

                    flag = true;
                    break;
                }
            }
        }

        if (flag) break;
    }

    if (!flag) cout << "IMPOSSIBLE\n";
}
```
:::


---

### [ZJ e289 美麗的彩帶](https://zerojudge.tw/ShowProblem?problemid=e289)

撰寫者：fishhh



---
