听说可以直接线性贪心,不过网上大部分做法都是三分。

显然最终不愉快度关于出成绩的时间是一个下凸的单峰函数,直接三分就好了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
typedef long long ll;
using namespace std; const int N=100100;
ll a,b,c,mn,ti[N],bi[N];
int n,m; ll jud(ll x){
ll res=0;
if (a<b){
ll tmp1=0,tmp2=0;
rep(i,1,m)
if (x<bi[i]) tmp1+=bi[i]-x; else tmp2+=x-bi[i];
if (tmp2>=tmp1) res+=tmp1*a; else res+=tmp2*a+(tmp1-tmp2)*b;
}else rep(i,1,m) if (x<bi[i]) res+=(bi[i]-x)*b;
rep(i,1,n) if (x>ti[i]) res+=(x-ti[i])*c;
return res;
} ll solve(){
ll l=1,r=100000;
while (l+2<r){
ll mid1=(2*l+r)/3,mid2=(l+2*r)/3,t1=jud(mid1),t2=jud(mid2);
if (t1==t2) l=mid1,r=mid2;
else if (t1<t2) r=mid2; else l=mid1;
}
ll t1=jud(l),t2=jud(r),t3=jud((2*l+r)/3),t4=jud((l+2*r)/3);
return min(min(t1,t2),min(t3,t4));
} int main(){
freopen("exam.in","r",stdin);
freopen("exam.out","w",stdout);
scanf("%lld%lld%lld",&a,&b,&c);
scanf("%d%d",&n,&m);
rep(i,1,n) scanf("%lld",&ti[i]);
rep(i,1,m) scanf("%lld",&bi[i]);
if (c==1e16){
mn=1e17;
rep(i,1,n) mn=min(mn,ti[i]);
printf("%lld\n",jud(mn));
return 0;
}
printf("%lld\n",solve());
return 0;
}
05-04 05:09
查看更多