BZOJ 杂题选记（9.7 - 9.13）

P5909 挂坠

经典贪心：\(n\) 个任务，有时长 \(w_i\) 和必须在 \(c_i\) 之前开始的限制。
交换邻项，可得策略按 \(w_i + c_i\) 从小到大排序。然后在按重量反悔贪心，发现两问一起解决了。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
int n;
struct node{ll w, c, r;
}a[N];
priority_queue<ll> q;
signed main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n;for(int i = 1; i <= n; ++i) cin >> a[i].c >> a[i].w, a[i].r = a[i].w + a[i].c;sort(a + 1, a + 1 + n, [](node x, node y){ return (x.r == y.r ? x.w < y.w : x.r < y.r); });ll sum = 0, ans = 0;for(int i = 1; i <= n; ++i){if(sum <= a[i].c){++ans;q.push(a[i].w);sum += a[i].w;}else{if(a[i].w < q.top()){sum += -q.top() + a[i].w;q.pop();q.push(a[i].w);}}}cout << ans << '\n' << sum << '\n';return 0;
}

P3620 数据备份

经典贪心：在 \(n\) 个数中选出 \(k\) 个不相邻的使得总和最小。
一个很 tricky 的策略，类似网络流退流的感觉，就是选了一个数 \(i\) 之后，删除左右两个数 \(l_i\)，\(r_i\)，并把 \(val_i \gets val_{l_i} + val{r_i} - val_{i}\) 重新丢进小根堆，每次选最小的。注意需要用链表维护邻项，因为可能出现二次反悔的情况。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
typedef pair<ll, int> pii;
int a[N], n, k, pre[N], nxt[N]; 
ll ans, val[N];
bitset<N> bk;
priority_queue<pii, vector<pii>, greater<pii> > q;
void del(int x){nxt[pre[x]] = nxt[x];pre[nxt[x]] = pre[x];bk[x] = 1;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n >> k;for(int i = 1; i <= n; ++i){cin >> a[i];pre[i] = i - 1, nxt[i] = i + 1;val[i] = a[i] - a[i - 1];if(i >= 2) q.emplace(val[i], i);}val[1] = val[n + 1] = 1e18;for(int i = 1; i <= k; ++i){while(bk[q.top().second]) q.pop();auto [dis, u] = q.top();q.pop();ans += dis;val[u] = val[pre[u]] + val[nxt[u]] - val[u];del(pre[u]), del(nxt[u]);q.emplace(val[u], u);}cout << ans;return 0;
}