NC20439. [SHOI2017]期末考试
描述
输入描述
第一行三个非负整数A,B,C，描述三种不愉快度，详见【问题描述】；第二行两个正整数n,m(1 ≤ n,m ≤ 105)，分别表示学生的数量和课程的数量；第三行n个正整数ti，表示每个学生希望的公布成绩的时间；第四行m个正整数bi，表示按照原本的计划，每门课程公布成绩的时间。1 ≤ N,M,Ti,Bi ≤ 100000,0 ≤ A,B,C ≤ 100000
输出描述
输出一行一个整数，表示最小的不愉快度之和。
示例1
输入:
100 100 2 4 5 5 1 2 3 1 1 2 3 3
输出:
6
说明:
由于调整操作产生的不愉快度太大，所以在本例中最好的方案是不进行调整; 全部C++(clang++ 11.0.1) 解法, 执行用时: 86ms, 内存消耗: 1960K, 提交时间: 2023-07-07 09:35:04
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N=100010;
ll t[N],y[N];
ll a,b,c;
ll n,m;
ll check(ll x)
{
ll p=0,q=0,res=0;
for(int i=1;i<=m;i++)
{
if(y[i]>=x) p+=y[i]-x;
else q+=x-y[i];
}
if(b<=a) res=p*b;
else
{
if(q>=p) res=p*a;
else res=q*a+(p-q)*b;
}
for(int i=1;i<=n;i++) if(t[i]<x) res+=(x-t[i])*c;
return res;
}
int main()
{
cin>>a>>b>>c;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>t[i];
for(int i=1;i<=m;i++) cin>>y[i];
ll l=1,r=*max_element(y+1,y+m+1);
while(l+10<r)
{
ll m=l+r>>1,mm=m+l>>1;
if(check(m)>=check(mm)) r=m;
else l=mm;
}
ll ans=2e18;
for(ll i=l;i<=r;i++) ans=min(ans,check(i));
cout<<ans<<endl;
return 0;
}