# SCIST S4 演算法課程_預處理&排序
:::info
時間：03/24 9:00 ~ 18:00
主題：預處理&排序
直播連結：https://www.youtube.com/watch?v=kUQkSaIK000
:::
## 課程內容
- 預處裡
- 質數篩
- 前綴和
- 排序
- 講義連結：https://hackmd.io/@sa072686/cp/%2F%40sa072686%2FrJpY0i7PS
# 題解
[TOC]
# 預處理
## [AtCoder typical90_d](https://hackmd.io/@sa072686/AtCoder_typical90_d)
撰寫者：百鬼真香
解法：預處理每個直排和橫排的和 $S_i, S_j$，在計算答案 $B_{i, j}$ 時就可以直接用 $S_i + S_j - A_{i, j}$ 了。
:::spoiler 參考程式
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 2005
int a[N][N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int h, w;
cin >> h >> w;
for(int i=0; i<h; i++)
for(int j=0; j<w; j++)
cin >> a[i][j];
int si[N], sj[N];
for(int i=0; i<h; i++){
int sum = 0;
for(int j=0; j<w; j++) sum += a[i][j];
si[i] = sum;
}
for(int j=0; j<w; j++){
int sum = 0;
for(int i=0; i<h; i++) sum += a[i][j];
sj[j] = sum;
}
for(int i=0; i<h; i++){
for(int j=0; j<w; j++)
cout << si[i] + sj[j] - a[i][j] << " ";
cout << "\n";
}
return 0;
}
```
:::
## [AtCoder typical90_at](https://hackmd.io/@sa072686/AtCoder_typical90_at)
撰寫者：fishhh
因為想要求的是 $A_i+B_i+C_i$ 是否為 $46$ 的倍數。
根據模的性質，$A_i+B_i+C_i$ 等價於 $(A_i \% 46)+(B_i \% 46)+(C_i \% 46)$
我們就可以知道，$46、46 \times2、46\times3....$ 之類的數字在這一題裡面可以看成是一樣的。
同樣的，$46+i、46 \times 2 +i、46\times 3 +i.....$ 也可以視為相同。
所以數列中的數只有 46 種（$0 \sim 45$），根據一點點枚舉的想法，我們可以透過枚舉數列 $A$ 裡面拿出餘數為 $x$ 的數，再枚舉數列 $B$ 內餘數為 $y$ 的數。
這時候我們就可以知道，從數列 $C$ 裡面拿出來的數字 $z$，應該要滿足 $x+y+z$ 是 $46$ 的倍數
稍微透過數學算一下，$z = 46 - (x+y)\%46$，就可以知道我們只要要從數列 $C$ 中，拿出餘數為 $z$ 的數就可以滿足題目要的。
:::spoiler
```cpp=
int a[100010],b[100010],c[100010];
int cnt_a[50],cnt_b[50],cnt_c[50];
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<=n;i++)cin>>c[i];
for(int i=1;i<=n;i++){
cnt_a[a[i]%46]++;
cnt_b[b[i]%46]++;
cnt_c[c[i]%46]++;
}
int ans = 0;
for(int x=0;x<46;x++){
for(int y = 0;y<46;y++){
int z = (46-(x+y)%46)%46;
ans += cnt_a[x]*cnt_b[y]*cnt_c[z];
}
}
cout<<ans<<"\n";
}
```
:::
## [TOJ 120](https://toj.tfcis.org/oj/pro/120/)
撰寫者：百鬼真香
解法：題目要求多個區間和，所以可以用前綴和。
注意：
1.因為前綴和需要把所有數加起來，所以經常需要 long long
2.計算區間和需要保證是由後面減前面，否則會出錯
:::spoiler 參考程式
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 200005
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
ll a[N];
for (int i = 0; i < n; i++)
cin >> a[i];
ll pre_sum[N] = {0};
for (int i = 0; i < n; i++)
pre_sum[i + 1] = pre_sum[i] + a[i];
int q;
cin >> q;
while(q--){
int a, b;
cin >> a >> b;
if(a > b) swap(a, b);
cout << pre_sum[b] - pre_sum[a - 1] << '\n';
}
return 0;
}
```
:::
## [AtCoder abc048_b](https://atcoder.jp/contests/abc048/tasks/abc048_b)
撰寫者：fishhh
題目要問的是，在 $[a \sim b]$ 之間有幾個數可以被 $x$ 整除。
我們可以知道一件事情，在一個連續的自然數數列中，可以被 $x$ 整除的數字的間隔會是 $x$。
也就是，當目前這個數模 $x$ 是 $0$ 那麼下一個出現可以被 $x$ 整除的數字會是 $x$ 個後，且一直保持這個規則。
前面看不懂沒關係(x
我們只需要這樣做，找到第一個 $\geq a$ 的 $x$ 的倍數，在找到第一個 $\leq b$ 的 $x$ 的倍數。
然後計算說中間的間距並且除以 $x$ 就可以了！
:::spoiler 參考程式
```cpp=
void solve(){
int a,b,x;
cin>>a>>b>>x;
a += (x-a%x)%x;
b -= b%x;
if(a<=b){
cout<<((b-a)/x)+1<<"\n";
}
else{
cout<<"0\n";
}
}
```
:::
## [CSES 1662](https://cses.fi/problemset/task/1662/)
撰寫者 : Paul
因為要算被 $n$ 整除的連續子區間數量，我們可以對前綴和 $mod$ $n$ 。可以把題目想成:前綴和 $mod$ $n$ 相同的組數，加上 $mod$ $n = 0$ 的前綴和序列數量。假設有 $k$ 個前綴和 $mod$ $n$ 有相同餘數，則這 $k$ 個前綴和可創造出的答案數量為 $k*(k-1)/2$ ( $k$ 個裡面選兩個且不排順序，因為前綴和只能夠後面的減前面的)。其中如果 $mod$ $n = 0$ 的前綴和序列也符合題目要求，要加進答案裡面。
因為 $a_i$ 可能出現負數，而且對負數取 $mod$ 會跑出負數，所以要加上 $n$ 再記錄下來。
:::spoiler 參考程式
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
int mod[200005];
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, a, sum=0, ans=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a;
sum+=a;
sum%=n;
if(sum<0) sum+=n;
mod[sum%n]++;
}
ans+=mod[0];
for(int i=0;i<n;i++)
{
ans+=(mod[i]*(mod[i]-1)/2);
}
cout<<ans<<endl;
}
```
:::
## [Kattis commercials](https://open.kattis.com/problems/commercials)
撰寫者：百鬼真香
因為每播一次廣告需要花 $P$ 元，而每次播廣告可以多收入 $a_{i}$ 元，所以可以先把每個廣告時段的收入減掉 $P$，接著計算哪個連需時段可以賺最多錢，也就是連續最大和，就可以了。
:::spoiler 參考程式
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 200005
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, p;
cin >> n >> p;
int a[N];
for(int i=0; i<n; i++){
cin >> a[i];
a[i] -= p;
}
int tmp = 0, ans = 0;
for(int i=0; i<n; i++){
tmp += a[i];
if(tmp > ans) ans = tmp;
else if(tmp < 0) tmp = 0;
}
cout << ans << endl;
return 0;
}
```
:::
---
# 排序
## [Kattis recount](https://open.kattis.com/problems/recount)
撰寫者：Eason
先排序好所有人的名字，方便紀錄每個名字出現幾次，最後找出出現最多次及第二多次的名字，並比較兩者是否相同。
另外這題也可以利用 map 來解。
:::spoiler 參考程式碼
```cpp=
#include<bits/stdc++.h>
#define weakson ios::sync_with_stdio(0), cin.tie(0);
using namespace std;
vector<string> v;
int main(){
weakson;
while (true){
string temp;
getline (cin, temp);
if (temp == "***") break;
v.emplace_back (temp);
}
sort (v.begin(), v.end());
int j;
pair <int, string> Max, Sec;
Max.first = 0;
Sec.first = -1;
for (int i = 0; i < v.size(); i = j){
for (j = i; j < v.size(); j++){
if (v[j] != v[i]) break;
}
pair<int, string> tmp = make_pair (j - i, v[i]);
if (tmp.first > Sec.first) Sec = tmp;
if (Sec.first > Max.first) swap (Sec, Max);
}
if (Max.first == Sec.first) cout << "Runoff!\n";
else cout << Max.second << '\n';
return 0;
}
```
:::
## [Kattis height](https://open.kattis.com/problems/height)
撰寫者：fishhh
這一題就是要求「插入排序」的交換次數。
如果不知道插入排序的話：
> 可以先看一下使用插入排序資料會長怎樣：https://youtu.be/kPRA0W1kECg?si=ZWsnPvuH4gXa-AaI&t=10
> 可以看講師的介紹：https://hackmd.io/@sa072686/cp/%2FfS7erjD_Q3ekLPbzzxSWRg#%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E6%B3%95-Insertion-Sort
> 或是題目的敘述：
一名學生將被選為排隊的第一人。然後，選擇另一個學生，找到隊伍中第一個比他高的人，站在那個人的前面，從而導致他後面的所有學生都後退以騰出空間。如果沒有比他高的學生，那麼他就會站在隊伍的最後。這個過程持續進行，一次一個學生，直到所有學生都排隊，此時學生將按身高順序排隊。
:::spoiler 參考程式
```cpp=
void solve(){
int t;
cin>>t;
while(t--){
int k;
cin>>k;
int ary[30];
for(int i=1;i<=20;i++){
cin>>ary[i];
}
int ans = 0;
for(int i=2;i<=20;i++){
for(int j=i;j-1>=1;j--){
if(ary[j]<ary[j-1]){
swap(ary[j],ary[j-1]);
ans++;
}
}
}
cout<<k<<" "<<ans<<"\n";
}
}
```
:::
## [AtCoder abc073_c](https://atcoder.jp/contests/abc073/tasks/abc073_c)
撰寫者：百鬼真香
讀完題目可以很直觀的發現，如果一個數字叫到 2 的倍數次，那他最後就不會在單子上，所以直接算出現奇數次的數字的個數就可以了。
如何計算每個數字出現的次數?
排序後，同樣的數字就會在一起，只要掃過一次就知道了。
:::spoiler 參考程式
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 200005
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a;
for(int i=0; i<n; i++){
int x;
cin >> x;
a.push_back(x);
}
sort(a.begin(), a.end());
int now = a[0], ans = 0, cnt = 1;
for(int i=1; i<n; i++){
if(a[i] == now) cnt++;
else{
ans += cnt & 1;
now = a[i];
cnt = 1;
}
}
ans += cnt & 1;
cout << ans << '\n';
return 0;
}
```
:::
## [AtCoder abc085_b](https://atcoder.jp/contests/abc085/tasks/abc085_b)
撰寫者：fishhh
<!-- 這個問題其實有一個專有名詞：「LIS」，可以透過 DP 在 $O(n \log n)$ 的時間內完成。
但這一題 $n$ 只有到 100 所以我們只要想一個比較簡單的方法就好。 -->
題目意思就是要對所有麻糬做排序，並且由大到小疊，但上下兩個麻糬之間一定要是嚴格大於。
可以發現這一題等價於把數列中重複的數挑出來。
那我們可以先排序後，計算有幾對數是一樣的，接下來只需要把它減掉即可。
:::spoiler
```cpp=
int ary[120];
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>ary[i];
}
for(int i=1;i<=n;i++){ //插入排序
for(int j=i-1;j>=1;j--){
if(ary[j+1]<ary[j]){
swap(ary[j+1],ary[j]);
}
}
}
int same = 0;
for(int i=2;i<=n;i++){
if(ary[i]==ary[i-1])same++;
}
cout<<n-same<<"\n";
}
```
:::
## [Kattis nothanks](https://open.kattis.com/problems/nothanks)
撰寫者：百鬼真香
題目：找所有連續數字的第一個數並加起來
解法 1：
直接的解法就是排序後，如果是連續數字，前後兩個數就只差 1，所以從小排到大後，只要一個數是前一個數加一，那就可以跳過他，否則就加上他。
特別的，排序後的第一個數一定是其中一個解，所以可以直接加上他。
:::spoiler 參考程式
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 90005
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int a[N];
for(int i=0; i<n; i++)
cin >> a[i];
sort(a, a+n);
int ans = a[0];
for(int i=1; i<n; i++){
if(a[i] == a[i-1] + 1) continue;
ans += a[i];
}
cout << ans << endl;
return 0;
}
```
:::
\
解法 2：
因為想到了所以不寫一下感覺就浪費了，以下為毒瘤，請謹慎考慮是否要浪費時間在這。
剛剛的解法時間是 $O(n\log{n})$，那可不可以優化成 $O(n)$?
題目的數字在 90000 內，所以我們可以用一個 01 陣列來表示一個數是否出現過，那麼題目就變成：有幾個連續的 1，並算出所有連續 1 的開頭的 index 和。
如何判斷一個連續 1 的區間：
一個連續 1 區間代表其前後都是 0，所以如果相鄰兩數 xor 等於 1 就代表這是一個連續 1 區間的開頭或結尾。
如何確定他是區間開頭：
如果 $a_i\ xor\ a_{i+1} = 1$，且 $a_{i+1} = 1$，那他就是開頭，否則就是結尾
這樣一來我們就可以 $O(n)$ 解了。
:::spoiler 參考程式
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 90005
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int a[N] = {0};
for(int i = 0; i < n; i++){
int x;
cin >> x;
a[x] = 1;
}
int ans = 0;
for(int i=1; i<N; i++)
ans += (a[i] ^ a[i-1]) * a[i] * i;
cout << ans << endl;
return 0;
}
```
:::
## [Kattis synchronizinglists](https://open.kattis.com/problems/synchronizinglists)
撰寫者：Eason
題目會給你很多個 $n$，對於每一個 $n$，會有兩組長度為 $n$ 的陣列 $a$、$b$。你要做的事把兩個陣列都分別排序好後（假設排序好的陣列叫做 $as$、$bs$），讓 $mp[as_i]=bs_i$，最後求 $mp[a_i]$。注意到 $a_i$ 的範圍是 $[-10000,10000]$，如果直接 $mp[a_i]$ 會出事，所以可以特判 $a_i<0$ 的時候就存在 $mp[10000-a_i]$，這樣就能保證索引值不為負。或者可以直接用 std::map，就不用擔心負數的問題了。
:::spoiler 參考程式碼
```cpp=
#include<bits/stdc++.h>
#define weakson ios::sync_with_stdio(0), cin.tie(0);
using namespace std;
int main(){
weakson;
int n;
while (cin >> n){
if (n == 0) break;
vector<int> a(n), b(n), cpa(n), mp(20005);
for (int i = 0; i < n; i++){
cin >> a[i];
cpa[i] = a[i];
}
for (int i = 0; i < n; i++){
cin >> b[i];
}
sort (cpa.begin(), cpa.end());
sort (b.begin(), b.end());
for (int i = 0; i < n; i++){
if (cpa[i] < 0) mp[10000 - cpa[i]] = b[i];
else mp[cpa[i]] = b[i];
}
for (int i = 0; i < n; i++){
if (a[i] < 0) cout << mp[10000 - a[i]] << '\n';
else cout << mp[a[i]] << '\n';
}
cout << '\n';
}
}
```
:::
## [AtCoder abc219_c](https://atcoder.jp/contests/abc219/tasks/abc219_c)
撰寫者：fishhh
這一題的意思是，題目會給一個長度為 $26$ 的排列，也就是題目希望的字典序。
例如，我們常用的字典序就是 $abcdefghijk.....$ 也就是 $a$ 最大，$b$ 第二大...。
因為我們會寫 merge sort 所以整個題目**與一般排序不同的地方只有「比較」這件事情上面，其餘的完全相同**。
但是，比較兩個字串的自定義字典序會很麻煩，所以我們只要寫一個程式來做比較就好，非常非常容易。
:::spoiler 參考程式碼
```cpp=
string order;
string ary[500010];
int pos[30];
bool great(string a,string b){ // 判斷 a 是否大於 b
for(int i=0;i<a.size();i++){
if(a[i]<b[i]){
return 1; //確實 a 大於 b
}
else if(a[i]>b[i]){ // a 小於 b
return 0;
}
}
// 有一個字串是另一個字串的子字串
// 例如 abcd 跟 abcdfvfge
// 這時候就比較大小，長度小的在前面
if(a.size()<=b.size()){
return 1;
}
return 0;
}
void solve(){
cin>>order;
for(int i=0;i<26;i++){
pos[order[i]-'a'] = i+1;
}
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>ary[i];
}
}
```
:::
## [Kattis conformity](https://open.kattis.com/problems/conformity)
撰寫者：Jun-an
這題要找出最受歡迎的「課程組合」的人數。
假設某個學生選了 $100$ $101$ $102$ $103$ $488$ 這五門課，
那麼選課組合就是 「$100$ $101$ $102$ $103$ $488$」。
不過每個課程組合都沒有照順序排，
因此計算每個課程組合有多少人選之前要先排序。
至於課程組合的部分，可以發現都是由 $5$ 個長度為 $3$ 的數字組成，
所以可以直接用 $long$ $long$ $int$ 儲存，或是你要用 $string$ 也行。
接著是要計算最受歡迎的課程組合，
排序過後會發現一樣的課程組合會排在一起，
因此只需要用一次 $for$ 迴圈掃過即可。
這裡補充一下，如果出現多種最受歡迎組合的選課人數一樣時，
需要全部加總。
:::spoiler 參考程式碼
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;
int course[10005][5];
long long save[10005];
int main() {
int n;
while (cin >> n && n != 0) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 5; ++j) {
cin >> course[i][j];
}
sort(course[i], course[i] + 5);
for (int j = 0; j < 5; ++j) {
save[i] = save[i] * 1000 + course[i][j];
}
}
sort(save, save + n);
int mx = 1, cnt = 1, res = 1;
for (int i = 1; i < n; ++i) {
if (save[i] == save[i - 1]) {
++cnt;
if (i == n - 1) {
if (cnt > mx) {
mx = cnt;
res = cnt;
}
else if (cnt == mx) {
res += cnt;
}
}
}
else {
if (cnt > mx) {
mx = cnt;
res = cnt;
}
else if (cnt == mx){
res += cnt;
}
cnt = 1;
}
}
cout << res << '\n';
// clear.
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 5; ++j) {
course[i][j] = 0;
}
save[i] = 0;
}
}
}
```
:::
## [CSES 1074](https://cses.fi/problemset/task/1074/)
撰寫者：fishhh
題目的意思：給你 $n$ 根木棍，可以對每一個選擇要增長或是縮短，並且操作完後每一根長度一樣。
假設我們決定要讓最後的長度為 $x$，那麼成本就會是 $\sum\limits^{n}_{i=1} |a[i] - x|$。
為了讓成本最小化，也就是 $\forall x \in \mathbb{N},min(\sum\limits^{n}_{i=1} |a[i] - x|)$
經過高中數學的知識洗禮，相信大家都知道只要是這個數列的中位數就可以找到最小值。
所以，我們只要將這個數列排序後，並且將 $x$ 設為中位數然後線性掃一次就可以算出答案了！
這一題就不附程式碼了～
## [Kattis toflur](https://open.kattis.com/problems/toflur)
撰寫者：fishhh
以下提供本人不太嚴謹的證明，假設由小排到大是 $a_1 \leq a_2 \leq a_3.... \leq a_n$，最後的分數是 $k$。
那麼，我們可以試著打亂它看看，例如說把 $a_5$ 與 $a_6$ 交換看看（因為打亂一定是一堆數字的交換）
喔對，先把裡面的 sigma 展開，會發現其中是一堆平方，也就是 ${a_1}^2 + 2 \times ({a_2}^2 + {a_3}^2 ... + {a_{n-1}}^2) + {a_n}^2$ 然後減掉兩兩相鄰的(乘積)*2
我們把 $a_5$ 跟 $a_6$ 交換本身對於前面的平方和是完全不會影響的。
且 $a_5$ 跟 $a_6$ 本身有參與到的兩兩乘積就只有 $a_4 \times a_5$ 與 $a_5 \times a_6$ 與 $a_6 \times a_7$
又可以知道，其中的 $a_5 \times a_6$ 完全沒有影響，那就先拿掉了。
一開始對分數的貢獻為：$-2(a_6 \times a_7 + a_4 \times a_5)$
交換後會變成：$-2(a_5 \times a_7 + a_4 \times a_6)$
所以我們只要比一下這兩個的大小即可。
1. 先把 -2 拿掉，記得一下我們最後求出來的結果要反過來一次。
- $(a_6 \times a_7 + a_4 \times a_5)$
- $(a_5 \times a_7 + a_4 \times a_6)$
2. 移項
變成是
- $a_4 \times (a_5-a_6)$
- $a_7 \times (a_5-a_6)$
可以發現 $a_4$ 明顯小於 $a_7$ （最最最一開始的定義）
但，$(a_5-a_6)$ 又是負的，所以上面的會大於下面的。
但但但，我們需要把結果反過來（因為有拿掉 $-2$）
所以，上面的貢獻小於下面，換句話說，如果變成下面那樣子的話，分數就會增加，但我們只想求分數的最小值，所以不做任何改變（由小到大）就可以得到分數最小值。
~~打太多字了，懶得寫程式。~~
## [Kattis judging](https://open.kattis.com/problems/judging)
撰寫者：百鬼真香
題目要求兩個 judge 中同樣的字串最多幾個，所以可以分別計算單一種結果共出現幾次，在兩邊的 judge 中取小的，就是一種結果的最多共同次數。
如何計算單一種結果共出現幾次?
因為要算同種字串出現幾次，用陣列很麻煩，所以可以用另一種資料結構叫 map
map 就像是自由版陣列，他可以把任意東西當作 index 也就是當作標籤，在這個標籤下有一個值，所以我們可以把這題的字串當作標籤，出現過幾次當作值，就可以簡單的使用它了。
:::spoiler 參考程式
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100005
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
map<string, int> mp1, mp2;
set<string> s;
cin >> n;
for (int i = 0; i < n; i++){
string x;
cin >> x;
mp1[x]++;
s.insert(x);
}
for (int i = 0; i < n; i++){
string x;
cin >> x;
mp2[x]++;
s.insert(x);
}
int ans = 0;
for(auto e:s)
ans += min(mp1[e], mp2[e]);
cout << ans << endl;
return 0;
}
```
:::
## [ZJ b966](https://zerojudge.tw/ShowProblem?problemid=b966)
撰寫者：Koying
講義有提供合併線段的解法，參考程式如下
:::spoiler Code
```cpp=
#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
pair<int,int> v[10005];
signed main()
{
int n;
cin >> n
for(int i=0;i<n;i++) {
cin >> v[i].first >> v[i].second;
}
sort(v,v+n); // 1,2 4,8 5,6 7,9
int a=v[0].first,b=v[0].second;
int ans=0;
for(int i=0;i<n;i++)
{
if(v[i].first>b)
{
ans+=b-a;
a=v[i].first;
b=v[i].second;
}
else if((v[i].second)>b) b=v[i].second;
}
ans+=b-a;
cout<<ans<<endl;
return 0;
}
```
:::
#### 另解 1（只需陣列的解法）：
可以觀察到，對於一個被線段覆蓋的區間（如 $[1, 5]$ 就是一個被 $[1, 4], [2, 5]$ 兩線段覆蓋的區間），其起終點一定是一個線段的起終點，因此我們只需要記錄所有線段的起點與終點位置即可。
假設有一個線段 $[1, 4]$，我們在 $1$ 的位置紀錄為 $+1$，代表這個位置多了一條線段，並在 $4$ 的位置紀錄為 $-1$，代表這個位置少了一條線段。
最後，將紀錄的數字做前綴和後得到的結果，就是每個位置的線段覆蓋**厚度**。只要計算 $> 0$ 的塊數就是答案。
時間複雜度：$\mathcal{O}(10^7)$
:::spoiler Code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int x[10005], y[10005];
int cnt[10000005];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
cnt[x[i]]++;
cnt[y[i]]--;
}
int ans = 0;
for (int i = 0; i < 10000005; i++) {
cnt[i] += cnt[i - 1];
ans += (cnt[i] > 0);
}
cout << ans << '\n';
}
```
:::
#### 另解 2（使用排序 + struct / pair）
同樣是使用紀錄頭尾的技巧，我們將頭尾座標及狀態包成一個 struct or pair（例如線段 $[1, 4]$ 包成 $(1, +1), (4, -1)$）並用陣列紀錄。
接著我們將這個陣列依照第一個元素（座標）排序，得到的結果便是從左到右的**狀態更新順序**。
接著我們就可以依序對每次狀態更新進行計算，並記錄以下變數：
- $now$：上一次更新到哪
- $cur$：現在座標
- $cnt$：線段覆蓋厚度
- $ans$：答案
對於每種狀態更新，只有兩種情況：
1. 原本沒有線段覆蓋，現在多了一個
2. 原本有線段覆蓋，現在多或少了一個
可以發現，能夠修改答案的情況只有第二種，因為在這個座標之前就有線段覆蓋了，所以我們就可以將答案 $ans$ 加上 $cur - now$，並將 $now$ 更新為 $cur$，就可以得到最終的答案
:::spoiler Code
```cpp=
#include <bits/stdc++.h>
using namespace std;
pair<int, int> e[20005];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
e[i * 2] = {x, 1};
e[i * 2 + 1] = {y, -1};
}
sort(e, e + n * 2);
int ans = 0, now = 0, cnt = 0;
for (int i = 0; i < n * 2; i++) {
if (cnt == 0) {
cnt += e[i].second;
now = e[i].first;
}
else {
cnt += e[i].second;
ans += e[i].first - now;
now = e[i].first;
}
}
cout << ans << '\n';
}
```
兩份解法的時間差異：
:::
## [Kattis Sort Of Sorting](https://open.kattis.com/problems/sortofsorting)
撰寫者：Eason
用內建sort寫cmp
:::spoiler 參考程式碼
```cpp=
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
bool cmp(string a, string b){
if (a[0] == b[0]){
if (a[1] == b[1]){
return false;
}
else{
return a[1] < b[1];
}
}
else{
return a[0] < b[0];
}
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
int n;
while (cin >> n){
if (n == 0) break;
string name[205];
for (int i = 0; i < n; i++){
cin >> name[i];
}
stable_sort (name, name + n, cmp);
for (int i = 0; i < n; i++){
cout << name[i] << '\n';
}
cout << '\n';
}
return 0;
}
```
```cpp=
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio; cin.tie(0); cout.tie(0);
#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> v2i;
typedef vector<v2i> v3i;
typedef vector<string> vs;
typedef vector<vs> v2s;
typedef vector<pii> vp;
typedef vector<vp> v2p;
typedef vector<bool> vb;
typedef vector<vb> v2b;
int n;
vs arr;
bool compare(string& a, string& b) {
return a.substr(0,2) <= b.substr(0,2);
}
void merge_sort(vs& arr, int l, int r) {
if (l + 1 >= r) {
return;
}
int mid = (l + r) >> 1;
merge_sort(arr, l, mid);
merge_sort(arr, mid, r);
vs temp(r - l);
int temp_index = 0;
int l_ptr = l;
int r_ptr = mid;
while (l_ptr < mid && r_ptr < r) {
if (compare(arr[l_ptr], arr[r_ptr])) {
temp[temp_index++] = arr[l_ptr++];
}
else {
temp[temp_index++] = arr[r_ptr++];
}
}
while (l_ptr < mid) {
temp[temp_index++] = arr[l_ptr++];
}
while (r_ptr < r) {
temp[temp_index++] = arr[r_ptr++];
}
for (int i = l; i < r; i++) {
arr[i] = temp[i - l];
}
}
void solve() {
while (true) {
cin >> n;
if (n == 0) {
break;
}
arr.resize(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
merge_sort(arr, 0, n);
for (string i : arr) {
cout << i << '\n';
}
cout << '\n';
}
}
signed main() {
fastio;
solve();
return 0;
}
```
:::
## [UVa 11462](http://domen111.github.io/UVa-Easy-Viewer/?11462)
撰寫者：Eason
直接排序好後輸出，要特別注意 Uva 有嚴格比對，行末不能輸出多餘的空格。
:::spoiler 參考程式碼
```cpp=
#include<bits/stdc++.h>
#define weakson ios::sync_with_stdio(0), cin.tie(0);
using namespace std;
int main(){
weakson;
int n;
while (cin >> n){
if (n == 0) break;
vector<int> v(n);
for (int i = 0; i < n; i++){
cin >> v[i];
}
sort (v.begin(), v.end());
for (int i = 0; i < v.size(); i++){
cout << v[i];
if (i != v.size() - 1) cout << ' ';
}
cout << '\n';
}
return 0;
}
```
:::
## [AtCoder abc208_c](https://atcoder.jp/contests/abc208/tasks/abc208_c)
撰寫者：百鬼真香
題目要平均發給每人糖果，如果有剩的就從 ID 小的開始一人給一個，所以我們可以用 ID 排序後，每個人有 K/N 個糖果，再從小到 K%N 一人給一個就發完了。
但是，題目要求用原本的順序輸出，所以我們需要在一開始記錄每個人的 index，並在輸出前照 index 排序，就是正確答案了。
因為每個人要記錄 ID、index、糖果數，所以可以利用 struct 來當作每個人。
:::spoiler sort cmp 的另外一種寫法
正常來說，要另外定義比較函式需要這樣寫：
```cpp=
bool cmp(int a, int b){
return a < b;
}
int main(){
int a[100];
...
sort(a, a+100, cmp);
}
```
不過，這樣寫還要開新的函式，要移動鼠標打斷思緒，感覺很不爽。
所以有一種不同的寫法可以把比較函式寫在 main 函式中，名為匿名函式，~~或許是因為不用取名~~
```cpp=
int main(){
int a[100];
...
sort(a, a+100, [](int a, int b){ return a < b; });// 匿名函式
}
```
這種寫法跟 cmp 的結構差不多
我們一樣需要兩個變數 $a, b$ 做比較 `(int a, int b)`
並在函式中寫上需要的比較條件 `{ return a < b; }`
最後在前面加上中括號，告訴他這是匿名函式 `[]`
就大功告成了 `[](int a, int b){ return a < b; }`
這種寫法可以用在簡單的比較函式上，因為為了幾個字母開一個函式實在麻煩，而且這種寫法更易讀也更好寫。
:::
:::spoiler 參考程式
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 200005
struct citizen{
ll id, i, v;
}a[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
ll n, k;
cin >> n >> k;
for(int i=0; i<n; i++){
cin >> a[i].id;
a[i].v = k / n;
a[i].i = i;
}
sort(a, a+n, [](citizen a, citizen b){ return a.id < b.id; });
for(int i=0; i < k%n; i++)
a[i].v++;
sort(a, a+n, [](citizen a, citizen b){ return a.i < b.i; });
for(int i=0; i<n; i++)
cout << a[i].v << "\n";
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet