NC20439

分析

设经过操作后所有成绩全部公布的时间为 ，所获得的不愉快度为 。
当 很小，那么大部分同学都能在其能忍受的时间 内知晓成绩，但是由于 很小， 的情况是很多的，为了使所有科目的成绩都在时间 内出来，就需要将大于 的 减小，那么就会因为多次修改 获得较多的不愉快度，因此 是比较大的；当 很大，虽然不用怎么修改 ，但是 会超出大部分同学的时限 ，因此 也是比较大的。
根据以上分析， 应当是一个下凸的单峰函数，可以用三分法找到极小值点。
接下来分析如何计算 的值。假设强制所有成绩全部公布的时间为 ，将 分为两部分，等待成绩公布获得的不愉快度，以及修改 使得对于任意 有 所获得的不愉快度。等待成绩公布获得的不愉快度可以直接简单累加，res+=C*(x-t[i])。接下来讨论修改 使得对于任意 有 所获得的不愉快度。若 显然将成绩公布时间大于 的课程全部使用操作 调整为 更优；若 显然要尽量使用操作 ，当公布时间小于 的课程全部因操作 导致公布时间推迟到 时，将剩下公布时间大于 的课程使用操作 处理。按照以上为规则，即可在 内得到 。

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#define ll long long
#define N 100003
using namespace std;
int t[N],b[N];
int n,m;
ll A,B,C;
ll f(int x)//出成绩的时间为x
{
    int i;
    ll res=0;
    for(i=1;i<=n;i++)
    {
        if(x>t[i])//到截止日期还没出成绩
        {
            res+=C*(x-t[i]);
        }
    }
    //计算更改截止日期的代价
    if(A<B)
    {
        ll extra,need;
        extra=need=0;
        for(i=1;i<=m;i++)
        {
            if(b[i]<x) extra+=x-b[i];
            else if(b[i]>x) need+=b[i]-x;
        }
        //多余的天数为extra，可以用来弥补超过x的天数need
        /*
            当公布时间小于x的课程全部因操作1导致公布时间推迟到x时
            将剩下公布时间大于x的课程使用操作2处理
        */
        if(extra>need) res+=A*need;
        else res+=A*extra+(need-extra)*B;
    }
    else//全部使用操作2
    {
        for(i=1;i<=m;i++)
        {
            if(b[i]>x)
            {
                res+=B*(b[i]-x);
            }
        }
    }
    return res;//获得f(x)
}
int main()
{
    cin>>A>>B>>C;
    cin>>n>>m;
    int i;
    for(i=1;i<=n;i++) scanf("%d",t+i);
    for(i=1;i<=m;i++) scanf("%d",b+i);
    int ans;
    /*
        特判
        当C很大，就要让x=min{t[i]}
        不能让任何一个同学等一天
        否则代价巨大
        也不能让x<min{t[i]}
        否则修改b[i]的代价也会变大
    */
    if(C==10000000000000000)
    {
        ans=0x3f3f3f3f;
        for(i=1;i<=n;i++) ans=min(ans,t[i]);
    }
    else//三分
    {
        int l,r;
        l=r=1;
        for(i=1;i<=n;i++) r=max(r,t[i]);
        while(r-l>=10)//预留的区间为10
        {
            int lmid=l+(r-l)/3;
            int rmid=r-(r-l)/3;
            if(f(lmid)>f(rmid))
            {
                ans=l;
                l=lmid+1;
            }
            else r=rmid-1;
        }
        while(l<=r)
        {
            if(f(l)<f(ans)) ans=l;
            l++;
        }
    }
    cout<<f(ans)<<endl;//输出
    return 0;
}