p1. 購買力#
Solution#
把價格 sort 然後照題目條件判斷一下。
AC code
signed main() {
hyper;
int n, d, a[3];
int cnt = 0, sum = 0;
cin >> n >> d;
rep(i,0,n) {
rep(j,0,3) cin >> a[j];
sort(a, a+3);
if(a[2] - a[0] >= d) {
++cnt;
sum += (a[0] + a[1] + a[2]) / 3;
}
}
cout << cnt << ' ' << sum << '\n';
}
p2. 流量#
Solution#
對於每個方案先開一個陣列把流量算好，然後算價格取最小值。
AC code
signed main() {
hyper;
int n, m, k;
int q[MN][MN], c[MN];
cin >> n >> m >> k;
rep(i,0,n) rep(j,0,m) cin >> q[i][j];
int mn = INF;
rep(x,0,k) {
rep(i,0,n) cin >> c[i];
int f[MN][MN];
rr(f,0);
rep(i,0,n) rep(j,0,m) f[c[i]][j] += q[i][j];
int sum = 0;
rep(i,0,m) rep(j,0,m) {
if(i == j) sum += f[i][j];
else sum += min(f[i][j], 1000) * 3 + max(f[i][j] - 1000, 0) * 2;
}
mn = min(mn, sum);
}
cout << mn << '\n';
}
p3. 切割費用#
Solution#
感覺是要考平衡樹，但 C++ 太方便了，直接用 set 的功能就可以做到。對切割的順序排序完從頭掃一次，維護一個 set 是之前切過的所有點，再把目前要切的點丟進 set 並用 set.find() 找到位置，他的前後位置就是要切的棒子的端點。時間複雜度 \(O(n \log n)\)。
AC code
signed main() {
hyper;
int n, L;
cin >> n >> L;
vi a(n);
rep(i,0,n) {
int x, y;
cin >> x >> y;
a[y-1] = x;
}
int ans = 0;
set<int> cut;
cut.insert(0);
cut.insert(L);
rep(i,0,n) {
cut.insert(a[i]);
auto it = cut.find(a[i]);
int l = *prev(it), r = *next(it);
ans += r-l;
}
cout << ans << '\n';
}
p4. 低地距離#
Solution#
老題目了，先對 x 再對 y 排序就變成 y 座標的 LIS 問題了。dp 解時間複雜度是 \(O(n^2)\)，用二分搜可以變成 \(O(n \log n)\) 才會過。注意這題是非嚴格遞增的 LIS，沒注意吃了好幾個 WA QQ。
AC code
signed main() {
hyper;
int n;
cin >> n;
vector<pii> a(n);
rep(i,0,n) cin >> a[i].fi >> a[i].se;
sort(a.begin(), a.end());
vector<int> lis;
for(auto [x, y]: a) {
if(lis.empty() || y >= lis.back()) lis.push_back(y);
else *upper_bound(lis.begin(), lis.end(), y) = y;
}
cout << lis.size() << '\n';
}