OI笔记 | 2022.9 做题记录
其中的 dp 和 模板题 被转移到新的专题中了。
线段覆盖
给出 $n$ 条线段的左端点 $l$ 和右端点 $r$。问最多能够选出多少条互不重叠的线段（端点可重叠）。
题解
贪心的典例，即按照右端点从小到大排序，能选则选。
可以这样感性地考虑：右端点越小，对之后线段的妨碍越少。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct line {
int l, r;
bool operator < (const line &t) const {
return r < t.r || (r == t.r && l > t.l);
}
} a[1000005];
int main() {
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i].l >> a[i].r;
sort(a + 1, a + n + 1);
int ans = 0;
int nr = a[1].l - 1;
for(int i = 1; i <= n; i++) {
if(a[i].l >= nr) {
ans++;
nr = a[i].r;
}
}
cout << ans;
}
活动安排问题
有若干个活动，第i个开始时间和结束时间是 $[Si,fi)$。
同一个教室安排的活动之间不能交叠，求要安排所有活动，最少需要几个教室？
题解
即求线段重叠个数的最大值，可用类似于扫描线的思想。
遇到左端点答案$+1$，右端点答案$-1$，维护最大值即可。
#include <bits/stdc++.h>
using namespace std;
struct point {
int pos;
bool type; // 0 : l ; 1 : r
bool operator < (const point &t) const {
return pos < t.pos;
}
};
vector <point> a;
inline int read() {...}
int main() {
int n = read(), ans = 0, tmp = 0;
for(int i = 1; i <= n; i++) {
point l, r;
l.pos = read(), r.pos = read();
l.type = 0, r.type = 1;
a.push_back(l);
a.push_back(r);
}
sort(a.begin(), a.end());
for(int i = 0; i < a.size(); i++) {
if(a[i].type == 0) tmp++;
else tmp--;
ans = max(tmp, ans);
}
printf("%d", ans);
return 0;
}
交换机器的最小代价
有 $N$ 台机器重量各不相等，现在要求把这些机器按照重量排序，重量从左到右依次递增。移动机器只能做交换操作，但交换机器要花费一定的费用，费用的大小就是交换机器重量的和。例如：$3$ $2$ $1$，交换$1$ $3$后为递增排序，总的交换代价为 $4$。给出 $N$ 台机器的重量，求将所有机器变为有序的最小代价。（机器的重量均为正整数）
题解
考虑每个数最终要去到哪个位置。将这个数指向它要去的位置上的数，最终会形成一个环。答案就是 这若干个环内的最小代价 之和。
考虑每个环的最小代价如何取。
分两种情况：
-
用这个环内最小的数$minn$来交换一遍。这样的做法$w=\sum\limits_{i=begin}^{end}(minn+a[i])=len\times minn +sum$。
-
用整个数组中最小的数$M$来交换一遍。这样多了两次交换，但总代价可能变小。$w=(M+minn)\times 2 + (len\times M + sum)$。
取两种情况的最小值。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 50005;
typedef long long ll;
int a[MAX_N], b[MAX_N];
inline int read() {...}
int main() {
ll n = read(), ans = 0;
for(int i = 1; i <= n; i++) {
a[i] = read();
b[i] = a[i];
}
sort(b + 1, b + n + 1);
for(int i = 1; i <= n; i++) {
if(a[i] == b[i] || a[i] == -1) continue; // a[i] == -1 <-> a[i] is used
int j = i;
ll sum = 0, len = 0;
while(a[j] != b[i]) { // 加和 a[i] 所在的环; a[j]为当前遍历到的环上的数
len++;
sum += a[j];
int k = lower_bound(b + 1, b + n + 1, a[j]) - b;
// 在 b 中 O(logn)查找 a[j] 的位置 k，则 a[k] 为环中 a[j] 的下一个位置
a[j] = -1;
j = k;
}
a[j] = -1;
ans += min(sum + len * b[i], sum + len * b[1] + (b[1] + b[i]) * 2);
}
cout << ans;
return 0;
}
卡车加油
一辆卡车，初始时距离终点 L，油量为 P，在起点到终点途中有 n 个加油站，每个加油站油量有限，而卡车的油箱容量无限，卡车在行车途中，每走一个单位的距离消耗一个单位的油量，给定 n 个加油站距离起点的距离 A[i] 以及油存储量 B[i]。问卡车是否能到达终点，如果可达，最少需要加多少次油，否则输出 −1。输入不保证有序。
题解
我们考虑经过加油站时将加油站的油暂存在优先队列里。
等到某一时刻油用完了，取出优先队列里的最大值加到车里。
这样，加到车里的次数就是最小的。
#include <bits/stdc++.h>
using namespace std;
priority_queue <int> o;
vector <int> t[1000001];
int main() {
int l, p, n, ans = 0;
cin >> l >> p >> n;
for(int i = 1; i <= n; i++) {
int a, b;
cin >> a >> b;
t[a].push_back(b);
}
for(int i = 1; i <= l; i++) {
p--;
if(i == l) break;
for(int j = 0; j < t[i].size(); j++) o.push(t[i][j]);
if(p == 0) {
if(o.empty()) {
cout << -1;
return 0;
}
p += o.top();
o.pop();
ans++;
}
}
cout << ans;
return 0;
}
小明爱换钱
小明非常喜欢换钱，这天他想到一个换钱游戏，游戏规则是这样的，从一件价值 $1$ 元的小物品开始。然后，经过反复的交换，不断增加手中物品的价值。在每次兑换中，如果您的物品价值大于或等于 $R$ 元，您可以兑换为 $V$ 元，花费时间成本为 $T$ 分钟。现在，你的任务是用尽量少的时间，帮助小明兑换到大于等于 $W$ 元。
题解
注意这里的兑换指的是 不论之前有多少钱，都直接变成 $V$ 。所以考虑按 $R$ 对每一条规则进行排序，然后利用优先队列，循环找出耗时最短的交换。
稍有些复杂，见代码。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5+5;
struct E {
int u, v, time;
bool operator < (const E &t) const {
return u < t.u;
}
};
struct change {
ll money, time;
bool operator < (const change &t) const {
return time > t.time;
}
};
E edge[MAX_N];
ll len = 1;
priority_queue<change> o;
inline ll read() {...}
void write(ll x) {...}
int main() {
ll n = read(), m = read();
for(int i = 1; i <= n; i++) {
edge[len].v = read();
edge[len].u = read();
edge[len].time = read();
len++;
}
sort(edge + 1, edge + len + 1);
change tmp, tt;
int i = 1, j = 1;
tmp.money = 1;
tmp.time = 0;
o.push(tmp);
while(!o.empty()) {
tt = o.top();
o.pop();
if(tt.money >= m) {
write(tt.time);
return 0;
}
for(i = j; i <= len; i++) {
if(tt.money < edge[i].u) break;
else if (tt.money < edge[i].v) {
tmp.money = edge[i].v;
tmp.time = edge[i].time + tt.time;
o.push(tmp);
}
}
j = i;
}
write(-1);
return 0;
}
小明爱配对
小明现在非常喜欢配对（？？？），这天有一队人(有男生也有女生)在小明面前排成了一排，每人都有一个技能值，老师给小明出了一道题目，让他来对这些人进行配对。配对有如下要求：
-
相邻的男女才能进行配对。
-
每次优先选择技能值差距最小的一对进行配对，如果不止有一对，那么选出最左边的那一对。
-
选出的人离开队列，空位由后面的人补上，这让原来不相邻的男女可能变成相邻的。
就这样一直选取，直到最后配对出现。这个问题难为住了小明，聪明的你可以帮助小明解决这个问题吗？
题解
模拟。注意用 vis 阻止已经配对过的人再次和别人配对。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 200010;
int v[MAX_N];
vector<pair<int, int>> ans;
bool vis[MAX_N], sex[MAX_N];
struct pa {
int a, b, d; // 配对 a 和 b，它们的技能值差值为 d
bool operator < (const pa &t) const {
return (d == t.d ? a > t.a : d > t.d);
}
};
priority_queue<pa> o;
inline ll read() {...}
void write(ll x) {...}
int main() {
int n = read();
char t;
for(int i = 1; i <= n; i++) {
cin >> t;
v[i] = read();
sex[i] = (t == 'B');
}
for(int i = 1; i < n; i++) if(sex[i] != sex[i + 1]) o.push({i, i + 1, abs(v[i + 1] - v[i])}); // 初始化所有可能的配对
while(!o.empty()) {
int a = o.top().a, b = o.top().b;
o.pop();
if(!vis[a] && !vis[b]) {
// a 和 b 是有效且当前最优的一组配对
ans.push_back({a, b});
vis[a] = vis[b] = 1;
while(a >= 1 && vis[a]) a--;
while(b <= n && vis[b]) b++;
if(a >= 1 && b <= n && sex[a] != sex[b]) o.push({a, b, abs(v[b] - v[a])});// 将两边的人处理成相邻的一对
}
}
write(ans.size()); putchar('\n');
for(int i = 0; i < ans.size(); i++) {
write(ans[i].first); putchar(' ');
write(ans[i].second); putchar('\n');
}
return 0;
}
♥