题解 P3745 【[六省联考2017]期末考试】

· · 题解

看了看楼下题解好多都是三分大佬+一堆函数的分析qwq

注意到本题有一个特点，学生的不愉快度只与最晚公布成绩的时间有关

看看题目数据范围，ti,bi<=10^5

所以很自然地想到一种思路

枚举最晚公布成绩的时间

假设我们当前枚举的最晚公布时间为t,那么我们显然要把所以大于t的课程公布时间调为t即可。

此时根据A与B的关系分类讨论:

若A>B 显然将大于t的课程全部使用操作2调为t更优

若A<B 显然能使用操作1则使用，当不能使用（公布时间小于t的课程全部因操作1导致公布时间推迟到t）时，只能将剩下大于t的课程使用操作2处理

A=B随意

对于C，因为最晚公布时间为t，统计一下对不愉快度的贡献即可

具体实现用3个前缀和，对所有情况取min

时间复杂度O（max(bi)） 我是直接从10^5开始枚举的

这种做法不开unsigned long long 居然会挂两个点qwq

#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=100000+5;
typedef unsigned long long ll;
const ll inf=100000000000000000ll;
ll bac[N],bac2[N],ti[N],bi[N],A,B,C,n,m;
int main(){
    scanf("%lld%lld%lld",&A,&B,&C);
    scanf("%lld%lld",&n,&m);
    ll sum1=0,t1=0,sum2=0,t2=0,sum3=0,t3=0;
    for(int i=1;i<=n;i++)
    scanf("%lld",&ti[i]),bac2[ti[i]]++,sum3+=ti[i],t3++;
    for(int i=1;i<=m;i++)
    scanf("%lld",&bi[i]),bac[bi[i]]++,sum2+=bi[i],t2++;
    ll ans=inf;
    for(ll i=100000;i>=1;i--){
        sum1+=i*bac[i],t1+=bac[i];
        sum2-=i*bac[i],t2-=bac[i];
        sum3-=i*bac2[i],t3-=bac2[i];
        if(!sum1)continue;
        ll tep=0;
        if(A<B){
            ll LQ1=sum1-t1*i,LQ2=t2*i-sum2;
            tep+=min(LQ1,LQ2)*A;
            LQ1-=min(LQ1,LQ2);
            if(LQ1)tep+=LQ1*B;
        }
        else {
            ll LQ1=sum1-t1*i;
            tep+=LQ1*B;
        } 
        tep+=(t3*i-sum3)*C;
        ans=min(ans,tep);
    }
    cout<<ans;
    return 0;
}