[洛谷 3745,loj 2141][六省联考2017]期末考试

题目链接

https://www.luogu.com.cn/problem/P3745

https://loj.ac/problem/2141

题解

枚举最晚公布成绩的时间 \(maxt\)。

对于公布成绩时间比 \(maxt\) 晚的，我们需要把它们提前。

分两种情况讨论：

• \(A \geq B\) 时，此时执行操作 2 最划算，直接将需要提前的科目全部提前即可；
• \(A \lt B\) 时，此时操作 1 最划算，我们将那些有空余时间的科目尽量延后，无法调整时再执行操作 2。

实现的时候，用前缀和维护总等待时间和调整量即可。

#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
ull t[100005],b[100005],s1[100005],s2[100005];
int p[100005],q[100005];
int main()
{
 ios::sync_with_stdio(false);
 ull A,B,C;
 int n,m;
 cin>>A>>B>>C;
 cin>>n>>m;
 for(int i=1;i<=n;i++)
  cin>>t[i];
 for(int i=1;i<=m;i++)
  cin>>b[i];
 sort(t+1,t+n+1);
 sort(b+1,b+m+1);
 for(int i=1;i<=n;i++)
  p[t[i]]++,s1[i]=s1[i-1]+t[i];
 for(int i=1;i<=m;i++)
  q[b[i]]++,s2[i]=s2[i-1]+b[i];
 ull ans=-1ull;
 ull cnt=n,x=0;
 for(int i=100000;i;i--)
 {
  cnt-=p[i];
  ull res=0;
  if(A>=B)
  {
   ull d=s2[m]-s2[m-x]-x*i;
   res+=max(B*d,0ull);
  }
  else
  {
   ull d1=s2[m]-s2[m-x]-x*i,d2=(m-x)*i-s2[m-x];
   if(d1<=d2)res+=max(d1*A,0ull);
   else res+=max(d2*A+(d1-d2)*B,0ull);
  }
  res+=max((cnt*i-s1[cnt])*C,0ull);
  x+=q[i];
  ans=min(ans,res);
 }
 cout<<ans<<endl;
 return 0;
}