闲话
调试约一个下午后发现极大值设小了。
Cardboard Box
考虑开两个堆 \(q_1\) 和 \(a_2\),一个存入所有一颗星星的取法,另一个存入所有两颗星星的取法。
每次两颗两颗比较,然后如果某一次取了一颗星星,那么(设这颗星星对应关卡编号为 \(i\))把 \(b_i - a_i\) 压入堆中。
还有一些别的细节,见代码。
代码:
#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
using namespace std;
int a[300010], b[300010], del[300010][3], ch[300010], w, n, ans, cnt, res;
map<int, int> mp;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q1, q2;
void debug(priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q) {
cout << "[ ";
while (!q.empty()) {
cout << "{ " << q.top().first << " " << q.top().second << " }" << " ";
q.pop();
}
cout << "]";
}
signed main() {
cin.tie(0) -> ios :: sync_with_stdio(false);
cin >> n >> w;
rep (i, 1, n) {
ch[i] = 0;
cin >> a[i] >> b[i];
q1.push({a[i], i});
q2.push({b[i], i});
}
if (w == 2 * n) {
rep (i, 1, n) {
ans += b[i];
}
cout << ans << "\n";
rep (i, 1, n) {
cout << 2;
}
cout << "\n";
return 0;
}
if (w % 2 == 1) {
q1.push({0, 0});
ch[0] = 1;
w++;
}
while (cnt < w) {
while (!q1.empty() && del[q1.top().second][1]) {
q1.pop();
}
while (!q2.empty() && del[q2.top().second][2]) {
q2.pop();
}
int a1 = 0x3f3f3f3f3f3f3f3f, id1 = 0, a2 = 0x3f3f3f3f3f3f3f3f, id2 = 0;
if (!q1.empty()) {
a1 = q1.top().first; id1 = q1.top().second; q1.pop();
while (!q1.empty() && del[q1.top().second][1]) {
q1.pop();
}
a2 = q1.top().first; id2 = q1.top().second; q1.pop();
}
int b1 = 0x3f3f3f3f3f3f3f3f, idb = 0;
if (!q2.empty()) {
b1 = q2.top().first; idb = q2.top().second; q2.pop();
}
if ((mp[id1] || mp[id2] || mp[idb]) && (id1 && id2 && idb)) {
assert(0);
}
if (a1 + a2 <= b1) {
// cout << a1 << " " << a2 << "\n";
cnt -= ch[id1] + ch[id2];
ch[id1]++; ch[id2]++;
// mp[id1] = mp[id2] = 1;
if (ch[id1] == 1) {
q1.push({b[id1] - a[id1], id1});
}
if (ch[id2] == 1) {
q1.push({b[id2] - a[id2], id2});
}
if (ch[id1] == 2) {
del[id1][1] = 1;
mp[id1] = 1;
}
if (ch[id2] == 2) {
del[id2][1] = 1;
mp[id2] = 1;
}
del[id1][2] = del[id2][2] = 1;
q2.push({b1, idb});
// cout << "q1: "; debug(q1); cout << "\n";
// cout << "q2: "; debug(q2); cout << "\n";
// ans += a1 + a2;
cnt += ch[id1] + ch[id2];
} else {
// cout << b1 << "\n";
cnt -= ch[idb];
ch[idb] += 2;
del[idb][1] = 1;
del[idb][2] = 1;
mp[idb] = 1;
q1.push({a1, id1});
q1.push({a2, id2});
// cout << "q1: "; debug(q1); cout << "\n";
// cout << "q2: "; debug(q2); cout << "\n";
// ans += b1;
cnt += ch[idb];
}
}
assert(cnt == w);
rep (i, 1, n) {
ans += (ch[i] == 1 ? a[i] : (ch[i] == 2 ? b[i] : 0));
assert(ch[i] <= 2);
res += ch[i];
}
// assert(res == w || res == w - 1);
cout << ans << "\n";
rep (i, 1, n) {
cout << ch[i];
}
cout << "\n";
}
标签:星星,q1,20,cout,训练,int,rep,笔记,两颗
From: https://www.cnblogs.com/IANYEYZ/p/18313315