# 上課例題
# b966: 第 3 題 線段覆蓋長度
給定一維座標上一些線段，求這些線段所覆蓋的長度，注意，重疊的部分只能算一次。
將每一條線段的起始點做排序，將起始位置設為第一條線段的頭，將結尾位置設為第一條線段的尾，再開始往後依序判別，
- 若現在的結尾位置已經超越了下一線段的頭，則將結尾位置定在下一個線段的尾
- 若現在的結尾位置未與下一線段的頭重疊，則使 cnt 加上目前累積的長度 (結尾位置 - 起始位置)
#include <bits/stdc++.h> | |
using namespace std; | |
typedef struct _node { | |
int s; // 頭 | |
int e; // 尾 | |
}Node; | |
bool cmp(Node p, Node q) { | |
if (p.s == q.s) return (q.e> p.e); | |
else return(p.s < q.s); | |
} | |
Node d[10000]; | |
int main() { | |
int n, cnt,start,end; | |
while (cin>>n) { | |
cnt = 0; | |
for (int i = 0; i<n; i++) { | |
cin>>d[i].s>>d[i].e; | |
} | |
sort(d, d + n, cmp); | |
for (int i = 0; i < n;i++) { | |
start = d[i].s; | |
end = d[i].e; | |
while ((i + 1 < n) && d[i + 1].s < end) { | |
if (d[i + 1].e <= end) i++; | |
else { | |
end = d[i + 1].e; | |
i++; | |
} | |
} | |
cnt += end - start; | |
} | |
cout<<cnt<<endl; | |
} | |
} |
# 延伸練習
# g277: 3. 幸運數字
內容
在 n 個人之中，每個人被分配到一個號碼，記錄為 a1,a2,…,an，這些號碼彼此都不相同，我們要找出當中最幸運的一個
已知在 [L,R] 區間之中，最幸運號碼定義為：
- 當 L=R 時，幸運號碼為 a [L]
- 當 L<R 時，找出當中最小號碼的位置 m，並將整個區間區分為左邊 [L,m-1] 與右邊 [m+1,R]，計算兩個區間各自的總和，總和比較大的區間即為幸運號碼所在的區間；如果兩個區間的總和相等，則幸運號碼位在右邊的區間，若區間不包含任何數字，總和視為 0
重複以上步驟直到收斂至 1. 時即可找到幸運號碼
尋找序列的最小值，可以透過先行將序列由小到大排序 (位置需另外紀錄)，
如果該序列的最小值落在區間內，即可作為中心點。
判斷左、右邊大小可以透過實作前綴和的方式計算區間的加總。
#include <bits/stdc++.h> | |
#define int long long | |
#define N 300005 | |
#define pii pair<int,int> | |
#define x first | |
#define y second | |
using namespace std; | |
int n,arr[N],pref[N]; | |
pii sorted[N]; | |
signed main(){ | |
cin>>n; | |
for(int i=1;i<=n;i++){ | |
cin>>sorted[i-1].x; | |
arr[i] = sorted[i-1].x; | |
sorted[i-1].y = i; | |
pref[i] = pref[i-1]+arr[i]; | |
} | |
sort(sorted,sorted+n); | |
int ind = 0,l = 1,r = n; | |
while(r>l){ | |
while(sorted[ind].y > r || sorted[ind].y < l) ind++; | |
int left = pref[sorted[ind].y-1] - pref[l-1]; | |
int right = pref[r] - pref[sorted[ind].y]; | |
if(left > right) | |
r = sorted[ind].y-1; | |
else | |
l = sorted[ind].y+1; | |
} | |
cout<<arr[l]<<endl; | |
} |
# a737: 10041 - Vito’s family
Vito 時常要拜訪所有的親戚，他希望從他的家到所有的親戚的家的距離的和為最小。
輸出從他的新家到所有的親戚的家的距離的和為最小為多少。
多個絕對值相加，最小值出現在排好數列的中位數時，用中位數帶入即可
#include<bits/stdc++.h> | |
using namespace std; | |
int main(){ | |
int n,t; | |
cin>>n; | |
while(n--){ | |
cin>>t; | |
int a[t]; | |
for(int i = 0;i<t;i++){ | |
cin>>a[i]; | |
} | |
sort(a,a+t); | |
int sum = 0; | |
int mid = a[t/2]; // 家的位置 | |
for(int i = 0;i<t;i++){ | |
sum += abs(mid - a[i]); | |
} | |
cout<<sum<<endl; | |
} | |
} |
# d150: 11369 - Shopaholic
林希是個購物狂。每次只要有買二送一的折扣 (送掉其中價錢最低的)，
她要買下店裡所有的商品。他想要減少她的支出。
你的工作便是找出林希最多可以省多少錢。
每一次結帳時，都取最貴的三個商品結帳，就可以讓送掉的金額最大。
#include <bits/stdc++.h> | |
using namespace std; | |
int main(){ | |
int n; | |
while(cin>>n){ | |
for(int i=0;i<n;i++){ | |
int m,sum=0; | |
cin>>m; | |
int p[m]; | |
for(int j=0;j<m;j++) | |
cin>>p[j]; | |
sort(p,p+m); | |
for(int j=1;m-3*j>=0;j++) | |
sum+=p[m-3*j]; | |
cout<<sum<<endl; | |
} | |
} | |
return 0; | |
} |
# d385: 10905 - Children's Game
你將會得到 N 個正整數，你可以將一個整數接在另一個整數之後以製造一個更大的整數。
排序完成後，全部字串照順序接起來即是答案。
例如給定的字串 "123"、“124”、“56”、90”，
按順序連接它們可得到 "1231245690"。
如果交換 "123"、“124”，可得到更好的結果 "1241235690"。
#include <bits/stdc++.h> | |
using namespace std; | |
bool cmp(string a,string b){ | |
return (a+b)>(b+a); | |
} | |
int main(){ | |
int n; | |
string s[50]; | |
while(cin>>n&&n){ | |
for(int i=0;i<n;i++) | |
cin>>s[i]; | |
sort(s,s+n,cmp); | |
for(int i=0;i<n;i++) | |
cout<<s[i]; | |
cout<<endl; | |
} | |
} |
