题意
有
n
n
n个关卡，第
i
i
i关可以花费
a
i
a_i
ai的代价打一颗星，
b
i
b_i
bi的代价打两颗星。保证
1
≤
a
i
<
b
i
≤
1
0
9
1\le a_i<b_i\le10^9
1≤ai<bi≤109，问要达到
w
w
w颗星最少花费。
题解
就是
h
d
u
6698.
C
o
i
n
s
hdu 6698.Coins
hdu6698.Coins 的弱化版。
h
d
u
hdu
hdu多校赛上是要查询要达到
1
→
2
n
1\to 2n
1→2n的所有每个
w
w
w的答案。
先把bi减去ai得到新的bi，要获取第二颗星的代价就是新的bi。
然后下面的硬币表示星，硬币组就是关卡。
先将硬币组分成两类，第一类 ai < bi，第二类 ai ≥ bi，并记 g(x) 为从第一类硬币组中符合限制地取出 x 枚硬币的最大价值和，令 h(x) 为从第二类硬币组中符合限制地取出 x 枚硬币的最大价值和。要求出 g，只需要将第一类的所有硬币按价值从小到大排序，则 g(x) 为前 x 个硬币的和。因为 ai < bi，可以发现在这个贪心方法中，如果选了 bi，则一定会先选了 ai；要求出 h，需要观察到：第二类硬币中最多只有一组硬币，会选了 ai 而没有选 bi。因为如果有两组硬币i, j, 满足 ai ≥ bi, aj ≥ bj，且某个方案只选了 ai, aj 而没有选 bi, bj，不失一般性，令 aj ≥ ai，那么有 aj ≥ ai ≥ bi，所以选 (ai, bi) 而不选 (aj , bj) 是个更优解，这时需要按 a + b 的值从小到大将第二类的每组硬币排序，则 h(2x) 就是前 x 组硬币的和，h(2x + 1) 就是“前 x 组加上不在前 x 组里的最小的 a”以及“前 x + 1 组中减去前 x + 1 组中最大的 b”两种方案中的较小值。求出 g, h 之后, 立即有
f
(
x
)
=
min
x
1
+
x
2
=
x
g
(
x
1
)
+
h
(
x
2
)
f(x) = \min_{x1+x2=x} g(x1)+h(x2)
f(x)=minx1+x2=xg(x1)+h(x2)，朴素地计算这个 min 卷积只能做到 O(n^2)，但是观察到 g 是个单调递增的凸函数而 h 是个单调递增函数，设
f
(
i
)
=
min
j
h
(
j
)
+
g
(
i
−
j
)
f(i) = \min_{j}h(j)+g(i-j)
f(i)=minjh(j)+g(i−j)，可以证明 p(x) 有单调性，利用决策单调性即可优化到 O(n log n)。
最后一段可以不看，因为CF这道题只需要求f(w)，所以直接枚举x1就行了。
输出方案就存一下编号。
CODE
#include <bits/stdc++.h>
using namespace std
;
inline void read(int &x
) {
char ch
; while(!isdigit(ch
=getchar()));
for(x
=ch
-'0';isdigit(ch
=getchar());x
=x
*10+ch
-'0');
}
typedef long long LL
;
const int MAXN
= 600005;
int n
, w
, cnt1
, cnt2
, mn
[MAXN
];
struct node
{
int x
, y
, id
;
inline bool operator <(const node
&o
)const {
return x
+y
< o
.x
+o
.y
;
}
}a
[MAXN
], b
[MAXN
];
LL g
[MAXN
], h
[MAXN
];
int c
[MAXN
];
int main
() {
read(n
), read(w
);
for(int i
= 1, x
, y
; i
<= n
; ++i
) {
read(x
), read(y
); y
-= x
;
if(x
< y
) a
[++cnt1
] = (node
){ x
, 0, i
}, a
[++cnt1
] = (node
){ y
, 0, i
};
else b
[++cnt2
] = (node
){ x
, y
, i
};
}
sort(a
+ 1, a
+ cnt1
+ 1);
sort(b
+ 1, b
+ cnt2
+ 1);
memset(g
, -1, sizeof g
); g
[0] = 0;
memset(h
, -1, sizeof h
); h
[0] = 0;
for(int i
= 1; i
<= cnt1
; ++i
) g
[i
] = g
[i
-1] + a
[i
].x
;
mn
[cnt2
+1] = 1000000000;
for(int i
= cnt2
; i
>= 1; --i
) mn
[i
] = min(mn
[i
+1], b
[i
].x
);
for(int i
= 1, j
, mx
= 0; i
<= cnt2
<<1; ++i
)
if(i
&1) j
= (i
+1)>>1, h
[i
] = min(h
[i
-1] + mn
[j
], h
[i
-1] + b
[j
].x
+ b
[j
].y
- mx
), mx
= max(mx
, b
[j
].y
);
else j
= i
>>1, h
[i
] = h
[i
-2] + b
[j
].x
+ b
[j
].y
;
LL ans
= 1ll<<60; int i
=0;
for(int j
= 0; j
<= w
; ++j
)
if(~g
[w
-j
] && ~h
[j
] && g
[w
-j
]+h
[j
] < ans
) ans
= g
[w
-j
]+h
[j
], i
= j
;
printf("%lld\n", ans
);
for(int j
= 1; j
<= w
-i
; ++j
) ++c
[a
[j
].id
];
int x
= (i
&1) ? (i
+1)>>1 : i
>>1;
for(int j
= 1; j
<= x
; ++j
) c
[b
[j
].id
] += 2;
if(i
&1) {
if(h
[i
] == h
[i
-1] + mn
[x
]) {
c
[b
[x
].id
] -= 2;
for(int j
= x
; j
<= cnt2
; ++j
)
if(b
[j
].x
== mn
[x
]) { ++c
[b
[j
].id
]; break; }
}
else {
int mx
= h
[i
-1] + b
[x
].x
+ b
[x
].y
- h
[i
];
for(int j
= 1; j
< x
; ++j
) if(b
[j
].y
== mx
) { --c
[b
[j
].id
]; break; }
}
}
for(int j
= 1; j
<= n
; ++j
) printf("%d", c
[j
]);
}
