# APCS 2021年01月題解
## 第一題 購買力
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=f605
### 解套
給n組數字，每組三個數字分別為a,b,c，求有幾組最大值減最小值大於等於一數字k
以及他們平均數的總和
### 題目分析
開兩個變數sum與sum2紀錄購買數量與總花費，接著直接吃輸入，用max與min函式得到最大值與最小值，若大於k就更新sum與sum2，最後輸出
### 解題流程
輸入$→$判斷$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,d,a,b,c,sum=0,sum2=0,mx,mn;
```
#### 輸入
```cpp=5
cin>>n>>d;
while(n--){
cin>>a>>b>>c;
```
#### 條件判斷、更新答案
```cpp=8
mx=max({a,b,c});
mn=min({a,b,c});
if(mx-mn>=d){
sum++;
sum2+=(a+b+c)/3;
}
```
其中max({a,b,c})等價於max(a,max(b,c))
#### 輸出
```cpp=15
cout<<sum<<" "<<sum2;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,d,a,b,c,sum=0,sum2=0,mx,mn;
int main(){
cin>>n>>d;
while(n--){
cin>>a>>b>>c;
mx=max({a,b,c});
mn=min({a,b,c});
if(mx-mn>=d){
sum++;
sum2+=(a+b+c)/3;
}
}
cout<<sum<<" "<<sum2;
}
```
## 第二題 流量
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=f606
### 解套
N/A
### 題目分析
直接按題目要求處理即可
因為第$i$個伺服器要傳到城市$j$的流量(即$Q[i][j]$)是固定的，所以先存著
而對每一個方案會有不同配置方式，所以對每一個方案計算需要的總花費，再取最小值即可
實作上我寫了一個函式$calc$計算每個方案的花費，先用一維陣列$server$紀錄每個伺服器在哪個城市，
再開一個二維陣列$city$，其中$city[i][j]$紀錄第$i$個城市要傳到第$j$個城市的總流量
因為$i$個伺服器會位在$server[i]$這個城市並對第$j$個城市有$Q[i][j]$的流量，
故遍歷所有可能，並讓$city[server[i]][j]$加上$Q[i][j]$就能得到所有城市間的流量傳送
最後依照題目的花費計算原則計算花費即可
最後複雜度$O(mnk)$
### 解題流程
輸入$→$遍歷、用calc函式計算、更新答案$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,m,k,q[50+10][50+10],server[50+10],city[50+10][50+10];
```
名稱與題述、前述相同($Q$改為$q$)
```cpp=22
int ans=INT_MAX;
```
ans預設為極大值
#### $calc$函式
```cpp=4
int calc(){
for(int i=0;i<m;i++)for(int j=0;j<m;j++)city[i][j]=0;
for(int i=0;i<n;i++)for(int j=0;j<m;j++){
city[server[i]][j]+=q[i][j];
}
int ans=0;
for(int i=0;i<m;i++)for(int j=0;j<m;j++){
if(i==j)ans+=city[i][j];
else{
if(city[i][j]<=1000)ans+=city[i][j]*3;
else ans+=3000+(city[i][j]-1000)*2;
}
}
return ans;
}
```
要記得讓$city$歸零(第5行)
花費計算依照題目敘述
1. 在同一個城市每單位流量1元(第11行)
2. 不同城市小於等於1000每單位流量3元(第13行)
3. 不同城市大於1000的部分每單位流量2元(第14行)
#### 輸入
```cpp=20
cin>>n>>m>>k;
for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>q[i][j];
```
#### 處理各方案
```cpp=23
while(k--){
for(int i=0;i<n;i++)cin>>server[i];
ans=min(ans,calc());
}
```
#### 輸出
```cpp=27
cout<<ans;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,m,k,q[50+10][50+10],server[50+10],city[50+10][50+10];
int calc(){
for(int i=0;i<m;i++)for(int j=0;j<m;j++)city[i][j]=0;
for(int i=0;i<n;i++)for(int j=0;j<m;j++){
city[server[i]][j]+=q[i][j];
}
int ans=0;
for(int i=0;i<m;i++)for(int j=0;j<m;j++){
if(i==j)ans+=city[i][j];
else{
if(city[i][j]<=1000)ans+=city[i][j]*3;
else ans+=3000+(city[i][j]-1000)*2;
}
}
return ans;
}
int main(){
cin>>n>>m>>k;
for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>q[i][j];
int ans=INT_MAX;
while(k--){
for(int i=0;i<n;i++)cin>>server[i];
ans=min(ans,calc());
}
cout<<ans;
}
```
## 第三題 切割費用
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=f607
### 解套
對一動態且由小到大排的陣列插入數字，每次花費是所插入數字後一個減前一個，求總花費
喔然後插入數字沒有照順序給，要自己處理
### 題目分析
首先要處理操作沒有照順序給的問題
一開始可能會想要對每個$\{x,i\}$按$i$排序之類的，但不用那麼麻煩
因為題目有說$n$最大只到$200000$，所以可以直接開陣列紀錄就好(用排的也會過，只是稍微慢一些。一開始我沒想太多也是用排的，後來才發現可以更快，~~對以前智障的自己感到傻眼~~)
接著是如何快速地得到答案
如果用vector然後每次遍歷找前後兩個數字複雜度會是$O(n^2)$，明顯超時
因此我們用c++內建的資料結構set來處理這個問題
每次先插入切的位置後，利用find與$++、--$找到前一個與後一個的指標，
取值後就能得到切的長度，全部加起來就是答案
時間複雜度$O(nlogn)$
### 解題流程
輸入$→$模擬切割過程$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,l,cut[200000+10],a,b;
long long int ans=0;
set<int>st;
```
n,l同題述，cut紀錄每個時間點切的地方，ans存答案且要記得開long long
#### 輸入
```cpp=7
cin>>n>>l;
for(int i=1;i<=n;i++){
cin>>a>>b;
cut[b]=a;
}
```
#### 切割模擬
```cpp=12
st.insert(0);
st.insert(l);
for(int i=1;i<=n;i++){
st.insert(cut[i]);
auto pre=st.find(cut[i]),nxt=st.find(cut[i]);
pre--;
nxt++;
ans+=*nxt-*pre;
}
```
一開始(第12、13行)先在set裡insert頭與尾，方便後續操作
接下來依序處理所有切割點，先把位置插入set裡後利用find找到位置，再用$++$和$--$找到前一個和後一個切割點的位置(第15-18行)，並把兩者取值後相減就是所切斷的長度(第19行)
#### 輸出
```cpp=21
cout<<ans;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,l,cut[200000+10],a,b;
long long int ans=0;
set<int>st;
int main(){
cin>>n>>l;
for(int i=1;i<=n;i++){
cin>>a>>b;
cut[b]=a;
}
st.insert(0);
st.insert(l);
for(int i=1;i<=n;i++){
st.insert(cut[i]);
auto pre=st.find(cut[i]),nxt=st.find(cut[i]);
pre--;
nxt++;
ans+=*nxt-*pre;
}
cout<<ans;
}
```
## 第四題 飛黃騰達
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=f608
### 解套
給定一些二維座標，求按某座標排序後，另一座標組成數列的最長遞增子序列(說明在後面)
### 題目分析
因為飛黃只能往右上方移動，所以其移動軌跡的x座標與y座標必定都是不嚴格遞增的，
因此我們如果按照其中一個座標由小到大排序，那麼對該座標而言行進順序一定是合法的
(如$[\{1,1\},\{2,5\},\{3,2\}]$按y座標排序後變成$[\{1,1\},\{3,2\},\{2,5\}]$)只看y座標確實是一直往上走
這時會發現既然某個方向的移動是全部合法的，那麼只要另一個方向的座標也都合法(不嚴格遞增)，就能找到一組合法的走法，而其中最長的就是我們要的答案
於是得到我們要的解法：將各座標按某方向排序後(我是用x)，求另一個方向的最長遞增子序列(LIS)
(LIS的做法說明在[這裡](https://web.ntnu.edu.tw/~algo/Subsequence.html#3))
唯一需要注意的是因為這題只需要非嚴格遞增就好($\{2,3\}$可以走到$\{3,3\}$)，所以lower_bound要改成upper_bound
最後時間複雜度$O(nlogn)$
### 解題流程
輸入$→$排序$→$找LIS$→$輸出
### 解題過程
#### define
```cpp=2
#define F first
#define S second
```
~~因為我懶得打6個字母~~
#### 變數宣告
```cpp=5
int n;
vector<pair<int,int>>v;
```
v存各座標
#### 輸入
```cpp=8
cin>>n;
v.assign(n,{});
for(int i=0;i<n;i++)cin>>v[i].F>>v[i].S;
```
第9行初始化v
#### 排序
```cpp=11
sort(v.begin(),v.end());
```
按x座標由小到大排
#### 找最長非嚴格遞增子序列
```cpp=13
for(auto i:v){
if(tmp.empty()||tmp.back()<=i.S)tmp.push_back(i.S);
else tmp[upper_bound(tmp.begin(),tmp.end(),i.S)-tmp.begin()]=i.S;
}
```
#### 輸出
```cpp=17
cout<<tmp.size();
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
int n;
vector<pair<int,int>>v;
int main(){
cin>>n;
v.assign(n,{});
for(int i=0;i<n;i++)cin>>v[i].F>>v[i].S;
sort(v.begin(),v.end());
vector<int>tmp;
for(auto i:v){
if(tmp.empty()||tmp.back()<=i.S)tmp.push_back(i.S);
else tmp[upper_bound(tmp.begin(),tmp.end(),i.S)-tmp.begin()]=i.S;
}
cout<<tmp.size();
}
```
Sign in with Wallet
Connect another wallet