Description
Solution
抽象题意，有两个序列
a
和b，可以通过以上方式改变
b
序列的权值，使得
∑ni=1max(0,max(bi)−ai)∗C 操作不愉快度最小。
观察上面的式子，我们发现
max(bi)
确定下来后，答案就确定下来了。
把
b
序列抽象成一排高度为bi的积木，操作就变成了用A花费移动一个积木，或者用B花费移走一个积木。
于是我们枚举一个高度
h
，这里也代表最晚成绩公布的时间，然后我们要调整这些积木，如下图：
贪心的想，如果发现A<B，那么肯定能移就移，红线（
h
）上的一部分（或全部）可移动到红线下，也就是所有在蓝线（h−1）或以下高度的都至少能放一个积木，剩余放不了的就直接消除。
如果
A≥B
，那么直接消除红色部分即可。
于是我们对于一个
h
，能通过前缀和快速求出把所有积木的高度限制在h即以下的花费。
回到原问题，我们枚举
h=max(bi)
，那么
∑ni=1max(0,h−ai)∗C
也可快速求出，于是两个加起来对
ans
取
min
即可。
这里的花费还满足三分性质，即如果不考虑输入，复杂度最优可达到
O(2log3n)
的。
Code
using namespace std;
int ti[N],b[N];
ll A,B,C;
ll qz[N],qb[N];
ll cn[N],cb[N];
int main()
{
int n,
m;
scanf(
"%lld %lld %lld",&A,&B,&C);
scanf(
"%d %d",&n,&
m);
int mx=
0,fw=
0;
fo(i,
1,n) scanf(
"%d",&ti[i]),fw=max(fw,ti[i]),cn[ti[i]]++,qz[ti[i]]+=ti[i];
fo(i,
1,
m) scanf(
"%d",&b[i]),cb[b[i]]++,qb[b[i]]+=b[i],mx=max(mx,b[i]);
fo(i,
1,max(fw,mx)) cn[i]+=cn[i-
1],qz[i]+=qz[i-
1];
fo(i,
1,max(fw,mx)) cb[i]+=cb[i-
1],qb[i]+=qb[i-
1];
if(C==
0) {
printf(
"0");
return 0;}
ll ans=inf;
fo(h,
1,mx)
{
ll o=cn[h]
*h-qz[h];
if(C>inf/
1000 && o)
continue;
ll t=o
*C;
if(B<=A) t+=B
*(qb[mx]-qb[h]-(cb[mx]-cb[h])
*h);
else
{
ll t1=cb[h-
1]
*h-qb[h-
1],t2=qb[mx]-qb[h]-(cb[mx]-cb[h])
*h;
if(t1>=t2) t+=A
*t2;
else t+=t1
*A+B
*(t2-t1);
}
if(ans>t) ans=t;
}
printf(
"%lld",ans);
}
