题解 CF436E 【Cardboard Box】
龙之吻—水货
2019-03-12 08:13:57
# Cardboard Box
## 题目大意
你正在玩一个名为割绳子的游戏，当前单元有 $n$ 关游戏，解锁下一单元需要 $w$ 颗星。对于每一关，得到 $1$ 颗星需要花费 $a_i$ 的时间，得到 $2$ 颗星需要花费 $b_i$ $(b_i > a_i)$，当然不得星不需要花费时间。问解锁下一单元至少需要多少时间，并输出方案。
## 解题报告
这题，可以一眼秒出一个背包做法或者一个比较优秀的DP做法，但由于 $1 \leq a_i \leq 10^9$，而 $1 \leq n \leq 3e5$，显然使用动归并不健康，于是考虑贪心做法。
这题，似乎看起来也可以直接贪心(也就是按照$a_i,b_i$的某种关系进行贪心选取)，但不幸的是，在CF比赛的时候某**t**姓红黑名网友尝试了直接贪心的做法，并且被 $hack$ 掉了，所以我们可能需要更好更稳定的贪心方法。
我们把每一关按照$b_i$从小到大排序，然后我们从$1$扫到$n$。
假设当前我们扫到$pos$，则表示的是 $1$ 到 $pos$ 的关卡中至少要得到一颗星， $pos + 1$ 到 $n$ 的关卡中至多得到一颗星。那么，显然 $1$ 到 $pos$ 的关卡中我们选取了 $pos$ 个 $a_i$，还需要从 $1$ 到 $pos$ 的$b_i - a_i$ 和 $pos + 1$ 到 $n$ 的 $a_i$ 这 $n$ 个数中选取前 $w - pos$ 小的，每次向前推进的时候需要删除一个 $a_i$，加入一个 $b_i - a_i$。显然类似线段树，树状数组，平衡树等数据结构可以很轻松地完成这个任务。(当然，如果出现了不合法的情况跳过即可)
考虑这样贪心的正确性，对于每一个 $pos$，如果 $pos$ 后面有选 $2$ 颗星的情况，显然不会比把其中的 $1$ 颗星转移到前面的关卡完成更优。而从 $1$ 扫到 $n$ ，则将所有可能的情况包含在内。~~感性理解一下这是正确的~~
至于如何输出方案，可以尝试在树上走路的方法，这里就不多说了 QwQ
附上我也不知道为什么写了这么长的代码 QwQ
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<tr1/unordered_map>
#include<vector>
class SegmentTree{
private :
static const int maxn = 6e5 + 7;
static const int INF = 1e9 + 7;
typedef long long ll;
struct Node{
int val, size;
ll sum;
Node *child[2];
Node() : val(0), size(0), sum(0) {
child[0] = child[1] = NULL;
}
};
int n;
Node *root, *tp, pool[maxn << 2];
Node *newNode() {
*++tp = Node();
return tp;
}
void update(Node *now) {
now->size = 0;
now->sum = 0;
for (register int i = 0; i < 2; i++) {
if (now->child[i]) {
now->size += now->child[i]->size;
now->sum += now->child[i]->sum;
}
}
}
void addVal(Node *now, int left, int right, int pos, int val) {
if (left == right) {
now->val = val;
now->sum += val;
now->size++;
return;
}
int mid = (left + right) >> 1;
if (pos <= mid) {
if (!now->child[0]) {
now->child[0] = newNode();
}
addVal(now->child[0], left, mid, pos, val);
} else {
if (!now->child[1]) {
now->child[1] = newNode();
}
addVal(now->child[1], mid + 1, right, pos, val);
}
update(now);
}
void delVal(Node *now, int left, int right, int pos, int val) {
if (left == right) {
now->sum -= val;
now->size--;
return;
}
int mid = (left + right) >> 1;
if (pos <= mid) {
if (!now->child[0]) {
now->child[0] = newNode();
}
delVal(now->child[0], left, mid, pos, val);
} else {
if (!now->child[1]) {
now->child[1] = newNode();
}
delVal(now->child[1], mid + 1, right, pos, val);
}
update(now);
}
ll query(Node *now, int left, int right, int tot) {
//printf("tot : %d\n", tot);
if (left == right) {
return 1ll * now->val * tot;
}
int leftsize = now->child[0] ? now->child[0]->size : 0;
int mid = (left + right) >> 1;
ll res = 0;
if (tot >= leftsize) {
if (now->child[0]) {
res += now->child[0]->sum;
}
if (tot > leftsize) {
res += query(now->child[1], mid + 1, right, tot - leftsize);
}
return res;
} else {
return query(now->child[0], left, mid, tot);
}
}
void search(Node *now, int left, int right, int tot, std::vector<int> &vec) {
if (!now) {
return;
}
if (left == right) {
while (tot--) {
vec.push_back(left);
}
}
int leftsize = now->child[0] ? now->child[0]->size : 0;
int mid = (left + right) >> 1;
if (tot >= leftsize) {
search(now->child[0], left, mid, leftsize, vec);
if (tot > leftsize) {
search(now->child[1], mid + 1, right, tot - leftsize, vec);
}
} else {
search(now->child[0], left, mid, tot, vec);
}
}
public :
void init(int x) {
n = x;
tp = pool;
root = newNode();
}
void addVal(int pos, int val) {
addVal(root, 1, n, pos, val);
}
void delVal(int pos, int val) {
delVal(root, 1, n, pos, val);
}
ll query(int tot) {
//printf("%d\n", tot);
//printf("%d : %d\n", root->size, tot);
return query(root, 1, n, tot);
}
void search(int tot, std::vector<int> &vec) {
search(root, 1, n, tot, vec);
//printf("%d %d\n", tot, vec.size());
}
};
class Solution{
private :
typedef std::pair<std::pair<int, int>, int> par;
typedef long long ll;
typedef std::vector<int>::iterator it;
static const int maxn = 3e5 + 7;
int n, m, p, res[maxn], num[maxn * 3], cnt, pos;
par val[maxn];
ll ans, sum, pre;
std::vector<int> vec, ps[maxn * 3];
//std::tr1::unordered_map<int, std::vector<int> > ps;
std::tr1::unordered_map<int, int> id;
SegmentTree tree;
public :
Solution() {
get();
solve();
}
void get() {
scanf("%d %d", &n, &m);
pos = std::max(m - n + 1, 1);
for (register int i = 1, x, y; i <= n; i++) {
scanf("%d %d", &x, &y);
//num[i] = x, num[i + n] = y;
num[i] = x, num[i + n] = y - x;
val[i] = std::make_pair(std::make_pair(y, x), i);
}
}
void solve() {
std::sort(val + 1, val + 1 + n);
std::sort(num + 1, num + 1 + (n << 1));
for (register int i = 1; i <= (n << 1); i++) {
if (num[i] != num[i - 1]) {
id[num[i]] = ++cnt;
}
}
tree.init(cnt);
for (register int i = 1; i < pos; i++) {
ans += val[i].first.second;
res[val[i].second]++;
tree.addVal(id[val[i].first.first - val[i].first.second], val[i].first.first - val[i].first.second);
}
for (register int i = pos; i <= n; i++) {
tree.addVal(id[val[i].first.second], val[i].first.second);
}
sum = tree.query(std::min(n, m));
p = pos - 1;
for (register int i = pos; i <= n; i++) {
pre += val[i].first.second;
tree.delVal(id[val[i].first.second], val[i].first.second);
tree.addVal(id[val[i].first.first - val[i].first.second], val[i].first.first - val[i].first.second);
if (std::min(n, m) <= (i - pos + 1)) {
continue;
}
ll q = tree.query(std::min(n, m) - (i - pos + 1));
if (pre + q < sum) {
sum = pre + q;
p = i;
}
}
tree.init(cnt);
for (register int i = 1; i < pos; i++) {
tree.addVal(id[val[i].first.first - val[i].first.second], val[i].first.first - val[i].first.second);
}
for (register int i = pos; i <= n; i++) {
tree.addVal(id[val[i].first.second], val[i].first.second);
}
printf("%lld\n", ans + sum);
for (register int i = pos; i <= p; i++) {
res[val[i].second]++;
tree.delVal(id[val[i].first.second], val[i].first.second);
tree.addVal(id[val[i].first.first - val[i].first.second], val[i].first.first - val[i].first.second);
if (i == p) {
tree.search(std::min(n, m) - (i - pos + 1), vec);
}
}
if (p == pos - 1) {
tree.search(std::min(n, m), vec);
}
for (register int i = 1; i <= n; i++) {
if (i <= p) {
num[i] = val[i].first.first - val[i].first.second;
} else {
num[i] = val[i].second;
}
}
for (register int i = 1; i <= n; i++) {
if (i <= p) {
ps[id[val[i].first.first - val[i].first.second]].push_back(val[i].second);
} else {
ps[id[val[i].first.second]].push_back(val[i].second);
}
}
for (register it i = vec.begin(); i != vec.end(); ++i) {
int now = *i;
//printf("%d\n", *i);
//printf("%d\n", *i);
//printf("%d\n", now);
res[ps[now].back()]++;
ps[now].pop_back();
}
for (register int i = 1; i <= n; i++) {
printf("%d", res[i]);
}
putchar('\n');
}
};
Solution sol;
int main() {}
/*QwQ*/
```