社区讨论

10分求调

P3745[六省联考 2017] 期末考试参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m09gnd9n
此快照首次捕获于
2024/08/25 19:02
2 年前
此快照最后确认于
2024/08/25 19:02
2 年前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,t[100005],b[100005];
ll A,B,C,ans;
ll calc1(int p){
	ll x=0,y=0;
	for (int i=1;i<=m;i++){
		if (b[i]<p)
		x+=p-b[i];
		else
		y+=b[i]-p;
	}
	return A<B?min(x,y)*A+(y-min(x,y))*B:y*B;
}
ll calc2(int p){
	ll sum=0;
	for (int i=1;i<=n;i++){
		if (t[i]<p)
		sum+=(p-t[i])*C; 
	}
	return sum;
}
int main(){
	cin>>A>>B>>C>>n>>m;
	for (int i=1;i<=n;i++)
	cin>>t[i];
	for (int i=1;i<=m;i++)
	cin>>b[i];
	sort(t+1,t+n+1);
	sort(b+1,b+m+1);
	if (C>=1e16){
		cout<<calc1(t[1]);
		return 0;
	} 
	ans=1e16;
	int l=1,r=100005;
	while (r-l>2){
		int mid1=l+(r-1)/3;
		int mid2=r-(r-1)/3;
		ll c1=calc1(mid1)+calc2(mid1);
		ll c2=calc1(mid2)+calc2(mid2);
		if (c1<=c2)
		r=mid2;
		else
		l=mid1;
	}
	for (int i=l;i<=r;i++)
	ans=min(ans,calc1(i)+calc2(i));
	cout<<ans;
	return 0;
} 

回复

0 条回复,欢迎继续交流。

正在加载回复...