[CF802N][jzoj5378]闷声刷大题

[CF802N][jzoj5378]闷声刷大题(贪心+wqs二分)

题目描述

大神犇 YCY现在有k道神题要刷（假定神题没有区别），刷一道题要分两个步骤，必须要先想出正解再写出正解。

他一共有n天时间可以刷题，但他每天最多只能想出一道题或写出一道题（你可以认为YCY在刷UF（Universe Final）的神题），可以在同一天想出一道题和写出一道题。

由于YCY每天的状态不同，第i天想一道题的代价为A[i]，写一道题的代价为B[i]。

定义刷一道题的代价为想的代价+写的代价，YCY想最小化k道题的代价和。

大神犇 YCY当然会做啦，于是把这个简单的问题交给你解决了。

输入格式

第一行两个整数n,k。

第二行n个整数，表示YCY每天想出一道题的代价

第三行n个整数，表示YCY每天写出一道题的代价

输出格式

仅一个数，表示最小的代价和

样例

样例输入

10 5
2 5 6 10 5 8 9 2 6 1 
6 6 5 5 7 7 3 6 8 6

样例输出

分析

可以想到一个朴素的贪心：每次取出合法的\((A[i]+B[j])_{min}\)，合法意味着前缀和\(S_i\ge 0\)，然后令\(A[i]=B[j]=\infin\)，进行\(m\)次即可，\(O(n^3)\)或者\(O(n^2)\)


const int N=3e5+10;

int n,m;
int A[N],B[N],S[N];
ll ans;

void Solve(){
	int Min=2e9,ida,idb,Minb=2e9,idb2,p=n+1; // p维护最长的合法后缀
	drep(i,n,1) {
		while(p>1 && (p-1>=i || S[p-1]>=1)) {
			p--;
			if(B[p]<Minb) Minb=B[p],idb2=p;
		}
		if(Minb<2e9 && A[i]+Minb<Min) Min=A[i]+Minb,ida=i,idb=idb2;
	}
	rep(i,ida,n) S[i]++;
	rep(i,idb,n) S[i]--;
	ans+=Min;
	A[ida]=B[idb]=1e9+10;
}

int main(){
	n=rd(),m=rd();
	rep(i,1,n) A[i]=rd();
	rep(i,1,n) B[i]=rd();
	
	rep(i,1,m) Solve();
	printf("%lld\n",ans);
}

设选了\(i\)对的答案为\(f_i\)由上面的贪心策略可以发现，\(f_{i+1}-f_i\ge f_{i}-f_{i-1}\)

这符合\(wqs\)二分的前置条件，所以我们二分斜率\(k\)，找到\(f_i-i\cdot k\)的最小值和出现位置

\(f_i-i\cdot k\)的维护，可以通过一个堆维护两种决策

1.替换掉之前的一个，个数不变

2.从还未选择的里面选一个，个数+1

这样就能在保证答案最小的情况下求出个数

const int N=1.5e5+10;

int n,m,A[N],B[N];
ll ans;

priority_queue <pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> que;

int Check(int mid) {
	ans=0;
	int cnt=0;
	while(!que.empty()) que.pop();
	drep(i,n,1) {
		que.push(make_pair(B[i]-mid,1)); 
		if(que.top().first+A[i]<=0) {
			ans+=que.top().first+A[i],cnt+=que.top().second;
			que.pop(),que.push(make_pair(-A[i],0));
		}
	}
	return cnt;
}
int main(){
	scanf("%d%d",&n,&m);
	rep(i,1,n) scanf("%d",A+i);
	rep(i,1,n) scanf("%d",B+i);
	int l=0,r=2e9,res;
	while(l<=r) {
		int mid=((ll)l+r)>>1;
		if(Check(mid)>=m) res=mid,r=mid-1;
		else l=mid+1;
	}
	Check(res),printf("%lld\n",ans+1ll*res*m);
}