CF436E Cardboard Box

\(n\) 个关卡，对每个关卡，你可以花 \(a_i\) 代价得到一颗星，也可以花 \(b_i\) 代价得到两颗星，也可以不玩。问获得 \(m\) 颗星最少需要多少时间。

给一种题解区还没有具体写但是是官方题解的做法。

思路

将关卡按 \(b_i\) 排序，发现如果我们对于关卡 \(x\)，如果花 \(b_x\) 的代价得到了两颗星星，那么如果答案要优秀，就必须在 \(1\sim x\) 的关卡中至少得到一颗星星。

证明：如果在 \(y(1\leq y< x)\) 位置没有得到一颗星星，那么我们可以花费 \(b_y\) 的代价在 \(y\) 处获得星星，同时取消掉 \(x\) 处取得的两颗星星，由于 \(b_y<b_x\)，所以在得到同样星星数量的情况下花费更小。

所以假设在前 \(L\) 个中都已经选了一颗星星，满足 \(\max(0,m-n)\leq L\leq \min(n,m)\)。那么可以认为只能在 \(1\sim L\) 的范围内考虑取两颗星星的情况，此时不会更劣。

此时的答案的一部分为 \(\sum_{i=1}^{L}a_i\)。

另一部分则是在 \(1\sim L\) 区间内多取一颗星星或在 \(L\sim n\) 的区间内取一颗星星的情况。

即可重集合 \(\{b_i-a_i|i\leq L\}\cup\{a_i|L<i\}\) 的前 \(m-L\) 小的元素的和。

实现

先将所有的 \(a_i\) 加入到一个数据结构中，从小到大枚举 \(L\) 时候，将 \(a_i\) 从数据结构中移除，\(b_i-a_i\) 加入。然后查询数据结构中前 \(m-L\) 小的元素和。

可以将 \(b_i-a_i,a_i\) 离散化。维护一颗线段树，线段树的每个区间上记录当前数据结构中该区间的数的个数 \(siz\) 和他们的和 \(sum\)。修改即为线段树单点修改。查询线段树上二分即可，注意一个叶子节点的 \(siz\) 可能大于要查询的数的个数，此时需要返回 \(siz\times val\)，其中 \(val\) 是该节点所对应的离散化数组的值的大小。

询问方案数我没有比较好的实现方法。我的方法是记录下答案最小时 \(L\) 的取值。然后将此时的 \(b_i-a_i\) 或 \(a_i\) 的值以及他们所对应的编号直接存下来排序，选前 \(m-L\) 个。

时间复杂度 \(O(n\log n)\)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>ttfa;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=300005;
int n,m,lis[N<<1],tot,bel[N];
ttfa arr[N];
inline int Loc(int x){return lower_bound(lis+1,lis+1+tot,x)-lis;}
struct node{ll a,b,d;int id;}a[N];
bool cmp(node x,node y){return x.b<y.b;}
int siz[N<<3];ll sum[N<<3];
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)
inline void pushup(int p){
	siz[p]=siz[ls]+siz[rs];
	sum[p]=sum[ls]+sum[rs];
}
void update(int p,int l,int r,int L,ll v,int f){
	if(l==r){siz[p]+=f;sum[p]+=f*v;return;}
	if(L<=mid)update(ls,l,mid,L,v,f);
	else update(rs,mid+1,r,L,v,f);
	pushup(p);
}
ll query(int p,int l,int r,ll k){
	if(l==r)return (ll)lis[l]*k;
	if(k<=siz[ls])return query(ls,l,mid,k);
	return sum[ls]+query(rs,mid+1,r,k-siz[ls]);
}

int main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i){
		a[i].a=read(),a[i].b=read();a[i].id=i;
		a[i].d=a[i].b-a[i].a;
		lis[++tot]=a[i].a,lis[++tot]=a[i].d;
	}
	sort(lis+1,lis+1+tot);
	tot=unique(lis+1,lis+1+tot)-lis-1;
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;++i)
		update(1,1,tot,Loc(a[i].a),a[i].a,1);
	ll pre=0,ans=0x3f3f3f3f3f3f3f3f;int lim=0;
	if(m<=n)ans=query(1,1,tot,m);
	//printf("%lld\n",ans);
	for(int i=1;i<=max(m-n,1)-1;++i){
		pre+=a[i].a;
		update(1,1,tot,Loc(a[i].a),a[i].a,-1);
		update(1,1,tot,Loc(a[i].d),a[i].d,1);
	}
	for(int i=max(m-n,1);i<=min(n,m);++i){
		pre+=a[i].a;
		update(1,1,tot,Loc(a[i].a),a[i].a,-1);
		update(1,1,tot,Loc(a[i].d),a[i].d,1);
		ll tmp=pre+query(1,1,tot,m-i);
		if(tmp<ans)ans=tmp,lim=i;
		//printf("%lld %lld\n",ans,lim);
	}
	printf("%lld\n",ans);
	//if(m==300000)printf("%d\n",lim);
	for(int i=1;i<=lim;++i)arr[i]={a[i].d,i},bel[a[i].id]=1;
	for(int i=lim+1;i<=n;++i)arr[i]={a[i].a,i};
	sort(arr+1,arr+1+n);
	for(int i=1;i<=m-lim;++i){
		if(arr[i].second<=lim)bel[a[arr[i].second].id]=2;
		else bel[a[arr[i].second].id]=1;
	}
	for(int i=1;i<=n;++i)
		printf("%d",bel[i]);
	putchar('\n');
	return 0;
}
/*
10 8
2 22
5 12
5 16
10 26
13 16
1 23
1 18
8 30
13 21
6 14
//上面是CF的一个数据点
*/

后记

特别感谢 recollector 大佬对本篇题解完成提供的帮助。