# 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
---
Sign in with Wallet
Connect another wallet