自动搬运

查看原文

来自洛谷，原作者为

	泅荼 **

搬运于2025-08-24 21:52:16，当前版本为作者最后更新于2018-05-15 09:25:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看了看楼下题解好多都是三分大佬+一堆函数的分析qwq

注意到本题有一个特点，学生的不愉快度只与最晚公布成绩的时间有关

看看题目数据范围，ti,bi<=10^5

所以很自然地想到一种思路

枚举最晚公布成绩的时间

假设我们当前枚举的最晚公布时间为t,那么我们显然要把所以大于t的课程公布时间调为t即可。

此时根据A与B的关系分类讨论:

若A>B 显然将大于t的课程全部使用操作2调为t更优

若A<B 显然能使用操作1则使用，当不能使用（公布时间小于t的课程全部因操作1导致公布时间推迟到t）时，只能将剩下大于t的课程使用操作2处理

A=B随意

对于C，因为最晚公布时间为t，统计一下对不愉快度的贡献即可

具体实现用3个前缀和，对所有情况取min

时间复杂度O（max(bi)） 我是直接从10^5开始枚举的

这种做法不开unsigned long long 居然会挂两个点qwq

#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=100000+5;
typedef unsigned long long ll;
const ll inf=100000000000000000ll;
ll bac[N],bac2[N],ti[N],bi[N],A,B,C,n,m;
int main(){
	scanf("%lld%lld%lld",&A,&B,&C);
	scanf("%lld%lld",&n,&m);
	ll sum1=0,t1=0,sum2=0,t2=0,sum3=0,t3=0;
	for(int i=1;i<=n;i++)
	scanf("%lld",&ti[i]),bac2[ti[i]]++,sum3+=ti[i],t3++;
	for(int i=1;i<=m;i++)
	scanf("%lld",&bi[i]),bac[bi[i]]++,sum2+=bi[i],t2++;
	ll ans=inf;
	for(ll i=100000;i>=1;i--){
		sum1+=i*bac[i],t1+=bac[i];
		sum2-=i*bac[i],t2-=bac[i];
		sum3-=i*bac2[i],t3-=bac2[i];
		if(!sum1)continue;
		ll tep=0;
		if(A<B){
			ll LQ1=sum1-t1*i,LQ2=t2*i-sum2;
			tep+=min(LQ1,LQ2)*A;
			LQ1-=min(LQ1,LQ2);
			if(LQ1)tep+=LQ1*B;
		}
		else {
			ll LQ1=sum1-t1*i;
			tep+=LQ1*B;
		} 
		tep+=(t3*i-sum3)*C;
		ans=min(ans,tep);
	}
	cout<<ans;
	return 0;
}