题目链接
题解
最后的答案决定于最后一个公布的成绩
显然这个是答案关于这个时间点是呈凸单调的
三分一下这个时间点
时间点固定，在这个时间前的人都会产生不愉快度，在这个时间前的科目可以往后挪
我们只需贪心选择在这个时间后的科目按哪种方式往前挪
复杂度\(O(nlogn)\)
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
using namespace std;
const int maxn = 100005,maxm = 100005;
const LL INF = 1000000000ll * 1000000000ll;
inline LL read(){
LL out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
return flag ? out : -out;
}
LL A,B,C;
int n,m,t[maxn],b[maxn],M;
LL cal(int lim){
LL re = 0,cnt = 0,d;
REP(i,n) if (t[i] < lim) {re += C * (lim - t[i]); if (C > 1e15) return INF;}
REP(i,m) if (b[i] < lim) cnt += lim - b[i];
REP(i,m) if (b[i] > lim){
d = b[i] - lim;
if (cnt && A < B){
if (cnt >= d) cnt -= d,re += A * d;
else re += A * cnt + B * (d - cnt),cnt = 0;
}
else re += B * d;
}
return re;
}
int main(){
A = read(); B = read(); C = read();
n = read(); m = read();
REP(i,n) t[i] = read();
REP(i,m) b[i] = read(),M = max(M,b[i]);
int l = 1,r = M,lmid,rmid;
while (r - l >= 3){
lmid = (l + l + r) / 3;
rmid = (r + l + r) / 3;
if (cal(lmid) >= cal(rmid)) l = lmid;
else r = rmid;
}
LL ans = INF;
for (int i = l; i <= r; i++)
ans = min(ans,cal(i));
printf("%lld\n",ans);
return 0;
}