BZOJ4868 Shoi2017期末考试（三分+贪心）

　　容易想到枚举最晚发布成绩的课哪天发布，这样与t和C有关的贡献固定。每门课要么贡献一些调节次数，要么需要一些调节次数，剩下的算贡献也非常显然。这样就能做到平方级别了。

　　然后大胆猜想这是一个凸函数三分就能A掉了。具体的，延迟最晚时间一方面会增加学生的不愉快度，这显然是时间越晚不愉快度增加量越大的，导数单增；另一方面使需要的调节次数减少，这个变化量显然越来越小，也即老师的不愉快度减少量越来越小，同样导数单增。所以两个函数的和也是导数单增的，即是一个凸函数。

　　注意存在C=10，稍微特判一下。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 100010

#define inf 2000000000000000000ll

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int A,B,n,m,a[N],b[N];

ll C,ans=inf;

ll calc(int k)

{

    ll s=;

    for (int i=;i<=n;i++)

    if (k>a[i]) if (C==10000000000000000ll) return inf+k;else s+=(k-a[i])*C;

    ll cnt1=,cnt2=;

    for (int i=;i<=m;i++)

    if (b[i]<k) cnt1+=k-b[i];

    else cnt2+=b[i]-k;

    if (B<A) s+=1ll*B*cnt2;

    else if (cnt1>=cnt2) s+=1ll*A*cnt2;

    else s+=1ll*A*cnt1+1ll*B*(cnt2-cnt1);

    return s;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4868.in","r",stdin);

    freopen("bzoj4868.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    cin>>A>>B>>C;

    n=read(),m=read();

    int l=,r=;

    for (int i=;i<=n;i++) a[i]=read();

    for (int i=;i<=m;i++) r=max(r,b[i]=read());

    while (l+<r)

    {

        int mid1=l+r>>,mid2=mid1+;

        if (calc(mid1)<calc(mid2)) r=mid2;

        else l=mid1;

    }

    for (int i=l;i<=r;i++) ans=min(ans,calc(i));

    cout<<ans;

    return ;

}