BZOJ 4868 [Shoi2017]期末考试

题目大意

有 $n$ 位同学，每位同学都参加了全部的 $m$ 门课程的期末考试，都在焦急的等待成绩的公布。

第 $i$ 位同学希望在第 $t_i$ 天或之前得知所有课程的成绩。如果在第 $t_i$​ 天，有至少一门课程的成绩没有公布，他就会等待最后公布成绩的课程公布成绩，每等待一天就会产生 $C$ 不愉快度。

对于第 $i$ 门课程，按照原本的计划，会在第 $b_i$ 天公布成绩。

有如下两种操作可以调整公布成绩的时间:

将负责课程 $X$ 的部分老师调整到课程 $Y$，调整之后公布课程 $X$ 成绩的时间推迟一天，公布课程 $Y$ 成绩的时间提前一天；每次操作产生 $A$ 不愉快度。 增加一部分老师负责学科 $Z$，这将导致学科 $Z$ 的出成绩时间提前一天；每次操作产生 $B$ 不愉快度。 上面两种操作中的参数 $X, Y, Z$ 均可任意指定，每种操作均可以执行多次，每次执行时都可以重新指定参数。

现在希望你通过合理的操作，使得最后总的不愉快度之和最小，输出最小的不愉快度之和即可。

我第一次读到这个题还以为每个同学填报的科目都不一样mmp

可以发现每个人的愤怒程度的原因都是一样的——取决于最后一个出成绩的学科出成绩的时间。

所以考虑枚举这个时间。对于每个时间二分，找出无法完成的学科，尝试用可以完成的学科填补（如果填补更划算），之后再尝试自我填堵后面的部分。

因为有前缀和所以虽然写起来比较麻烦但是是$O(n \log n)$的。

#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100010
int n,m,t[N],b[N],pt,pb;
long long A,B,C,vt[N],vb[N],res,ans=0x3f3f3f3f3f3f3f3fll;
int main()
{
	scanf("%lld%lld%lld%d%d",&A,&B,&C,&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",t+i);
	for(int i=1;i<=m;++i) scanf("%d",b+i);
	sort(t+1,t+n+1);
	sort(b+1,b+m+1);
	for(int i=1;i<=n;++i) vt[i]=vt[i-1]+t[i];
	for(int i=1;i<=m;++i) vb[i]=vb[i-1]+b[i];
	for(int i=0;i<=t[n];++i)
	{
		res=0;
		while(pt<n&&t[pt+1]<=i) pt++;
		while(pb<m&&b[pb+1]<=i) pb++;
		res+=(1ll*pt*i-vt[pt])*C;
		if(A<B)
		{
			long long tmp=min(1ll*i*pb-vb[pb],vb[m]-vb[pb]-1ll*i*(m-pb));
			res+=tmp*A+max(0ll,(vb[m]-vb[pb]-1ll*i*(m-pb)-1ll*i*pb+vb[pb]))*B;
		}
		else res+=(vb[m]-vb[pb]-1ll*i*(m-pb))*B;
		if(res<0) continue;
		ans=min(ans,res);
	}
	printf("%lld\n",ans);
	return 0;
}