「SHOI2017」期末考试

题意：$n$ 位同学参加了全部的 $m$ 门课程的期末考试，第 $i$ 位同学希望在 $t _{i}$ 天及之前知道所有课程成绩，若在 $t _{i}$ 天成绩未公布完全，他就会等待最后公布成绩的课程公布成绩，每等一天会产生 $\text{C}$ 不愉快度。第 $i$ 门课程原本会在第 $b _{i}$ 天公布成绩。现在有两种操作可以调整公布成绩的时间：

1. 将负责课程 $\text{X}$ 的部分教师调到课程 $\text{Y}$，调整后课程 $\text{X}$ 的公布时间推迟一天，课程 $\text{Y}$ 的公布时间提前一天，每次操作产生 $\text{A}$ 不愉快度；
2. 增加部分老师负责课程 $\text{Z}$，这将使课程 $\text{Z}$ 的公布时间提前一天，每次操作产生 $\text{B}$ 不愉快度。

你可以多次执行操作，$\text{X,Y,Z}$ 由你自己指定，现在请你通过合理操作使得总不愉快度最小，输出最小不愉快度。

数据范围与约定：

Case #	$n,m,t _{i},b _{i}$	$\text{A,B,C}$
1,2	$1\le n,m,t _{i},b _{i}\le 2000$	$\text{A,B}=10 ^{9},0\le \text{C}\le 10 ^{2}$
3,4	$1\le n,m,t _{i},b _{i}\le 2000$	$0\le \text{A,C}\le 10 ^{2},\text{B}=10 ^{9}$
5,6,7,8	$1\le n,m,t _{i},b _{i}\le 2000$	$0\le \text{B}\le \text{A}\le 10 ^{2},0\le \text{C}\le 10 ^{2}$
9,10,11,12	$1\le n,m,t _{i},b _{i}\le 2000$	$0\le \text{A,B,C}\le 10^{2}$
13,14	$1\le n,m,t _{i},b _{i}\le 10 ^{5}$	$0\le \text{A,B}\le 10 ^{5},\text{C}=10 ^{16}$
15,16,17,18,19,20	$1\le n,m,t _{i},b _{i}\le 10 ^{5}$	$0\le \text{A,B,C}\le 10 ^{5}$

解析：我们可以发现，学生的不愉快度只与最后出成绩的时间有关，且出成绩的时间越晚，学生的不愉快度单调递增，但老师的不愉快度是单调递减的。两个加起来是一个单谷函数，所以可以三分。我们三分最后出成绩的时间 $x$，现在的问题就是如何在最后出成绩的时间 $x$ 定下来的情况下计算最小的不愉快度。我们贪心的使用操作，设 $u$ 表示所有课程能提前的天数之和，$v$ 表示所有课程需要推迟的天数之和。如果 $\text{A}\ge \text{B}$，且第二个操作没有负面影响，那么我们显然将需要推迟的课程全部使用第二个操作提前至 $x$ 最优，它造成的不愉快度为 $v\cdot \text{B}$；如果 $\text{A<B}$，那么我们优先考虑使用第一个操作来提前，对于本来就在 $x$ 之前公布成绩的课程，我们对它们使用第一个操作延后至 $x$，这样做第一个操作是没有负面影响的，剩下的再用第二个操作即可，它所造成的不愉快度为 $u\cdot \text{A}+(v-u)\cdot \text{B}$。最后我们再把剩下的需要等待的 $\text{C}$ 的不愉快度加上即可求出总共的不愉快度。综上，我们先将 $t _{i},b _{i}$ 从小到大排序，如果等待的不愉快度 $\text{C}$ 过大，那么我们需要尽早知道所有成绩，答案就是成绩公布时间在 $t _{1}$ 的总不愉快度；否则我们就三分最后出成绩的时间即可。注意可能不止一个最优解，所以我们三分到一个较小的区间取最小值即可。时间复杂度为 $O(n\log (\max t))$

#include<cstdio>
#include<algorithm>
using namespace std;
long long n,m,t[101010],b[101010];
long long A,B,C,ans;
long long count(long long x)//贪心统计操作产生的不愉快度
{
	long long u=0;
	long long v=0;
	for(int i=1;i<=m;i++)
		if(x>b[i])
			u+=x-b[i];
		else
			v+=b[i]-x;
	if(A<B)
		return min(u,v)*A+(v-min(u,v))*B;
	else
		return v*B;
}
int main()
{
	int i,j;
	scanf("%lld%lld%lld%lld%lld",&A,&B,&C,&n,&m);
	for(i=1;i<=n;i++)
		scanf("%lld",&t[i]);
	for(i=1;i<=m;i++)
		scanf("%lld",&b[i]);
	sort(t+1,t+n+1);
	sort(b+1,b+m+1);
	if(C>=1e16)
		ans=count(t[1]);
	else
	{
		ans=1e16;
		long long l=1,r=200005;
		while(r-l>5)
		{
			long long mid=l+(r-l)/3;
			long long mmid=r-(r-l)/3;
			long long f1=count(mid);
			long long f2=count(mmid);
			for(i=1;i<=n;i++)
				if(t[i]<mid)
					f1+=C*(mid-t[i]);//加上等待产生的不愉快度
			for(i=1;i<=n;i++)
				if(t[i]<mmid)
					f2+=C*(mmid-t[i]);
			if(f1<=f2)
				r=mmid;
			else
				l=mid;
		}
		for(i=l;i<=r;i++)
		{
			long long x=count(i);
			for(j=1;j<=n;j++)
				if(t[j]<i)
					x+=C*(i-t[j]);
			ans=min(ans,x);//在三分出的(l,r)的范围内求最小值
		}
	}
	printf("%lld",ans);
	return 0;
}