http://www.lydsy.com/JudgeOnline/problem.php?id=4868
假设 最晚出成绩的是第i天
预处理 cnt[i] 表示 有多少个学生 期望出成绩的那一天 <i
sum[i] 表示 对应cnt[i] 那些学生 的 t 之和
比如 i=5，有4个学生 期望1 2 4 8 出成绩，那么 sum[5]=1+2+4=7，cnt[5]=3
假设 最晚出成绩的是第i天
学生的不愉悦度= (cnt[i]*i-sum[i])*C
类似的方法，算出 当前i下，能提前 某些 科目多少天，能推迟某些科目多少天
more_cnt[i] 表示有多少个科目 期望出成绩的那一天 >i
more_sum[i] 表示 对应more_cnt[i]那些科目的 b 之和
less_cnt[i] 表示有多少个科目 期望出成绩的那一天 <i
less_sum[i] 表示 对less_cnt[i]那些科目的 b 之和
需要提前的总天数=more_sum[i]-more_cnt[i]*i，记为need
可以推迟的总天数=less_cnt[i]*i-less_sum[i]，记为have
如果B<=A，那就只 提前，不愉悦度为need*B
如果A<=B，看看可以推迟的 天数 是否>=要 提前的天数
如果>=,那就只 用A，不愉悦度为 need*A
否则，能用A的用A，剩下的用B，不愉悦度为 have*A + （need-have）*B
在预处理出那些数组后，所有的计算都是O（1）的，总时间复杂度为O（n）
三分可以把求解过程优化到 logn
注意有C=1e16，直接乘的话会爆long long
这种情况下一定是 提前科目出成绩的时间，特判即可
考试的时候，特判错了，丢了10分，w(ﾟДﾟ)w
C=1e16，直接学生不愉悦度为 inf，应该是 最晚时间早于所有的期望时间，不愉悦度为0，其余的是inf啊啊啊啊
#include<cstdio>
#include<iostream> using namespace std; #define N 100001 #define min(a,b) ((a)<(b) ? (a) : (b))
#define max(a,b) ((a)>(b) ? (a) : (b)) typedef long long LL; int t[N],b[N];
//subject
int less_cnt[N],more_cnt[N];
LL less_sum[N],more_sum[N]; //student
int cnt[N];
LL sum[N]; template<typename T>
void read(T &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} int main()
{
freopen("exam.in","r",stdin);
freopen("exam.out","w",stdout);
int A,B,n,m;
LL C;
read(A); read(B); read(C);
read(n); read(m);
int x,mx=;
for(int i=;i<=n;++i)
{
read(x);
t[x]++;
}
for(int i=;i<=m;++i)
{
read(x);
b[x]++;
mx=max(mx,x);
}
for(int i=mx-;i;--i)
{
more_cnt[i]=more_cnt[i+]+b[i+];
more_sum[i]=more_sum[i+]+1LL*b[i+]*(i+);
}
for(int i=;i<=mx;++i)
{
cnt[i]=cnt[i-]+t[i-];
sum[i]=sum[i-]+1LL*t[i-]*(i-);
less_cnt[i]=less_cnt[i-]+b[i-];
less_sum[i]=less_sum[i-]+1LL*b[i-]*(i-);
}
LL student,subject;
LL ans=1e18;
LL have,need;
for(int i=;i<=mx;++i)
{
if(C<1e16) student=(1LL*cnt[i]*i-sum[i])*C;
else
{
if(1LL*cnt[i]*i-sum[i]) student=1e18;
else student=;
}
if(B<=A) subject=(more_sum[i]-1LL*more_cnt[i]*i)*B;
else
{
have=1LL*less_cnt[i]*i-less_sum[i];
need=more_sum[i]-1LL*more_cnt[i]*i;
if(have>=need) subject=need*A;
else subject=have*A+(need-have)*B;
}
ans=min(ans,student+subject);
}
cout<<ans;
return ;
}