洛谷 P3745 [六省联考2017]期末考试

传送门 $\looparrowright$

题目描述

有 $n$ 位同学，每位同学都参加了全部的 $m$ 门课程的期末考试，都在焦急的等待成绩的公布。
第 $i$ 位同学希望在第 $t_i$ 天或之前得知所有课程的成绩。如果在第 $t_i$ 天，有至少一门课程的成绩没有公布，他就会等待最后公布成绩的课程公布成绩，每等待一天就会产生 $C$ 不愉快度。
对于第 $i$ 门课程，按照原本的计划，会在第 $b_i$ 天公布成绩。
有如下两种操作可以调整公布成绩的时间:
① 将负责课程 $X$ 的部分老师调整到课程 $Y$，调整之后公布课程 $X$ 成绩的时间推迟一天，公布课程 $Y$ 成绩的时间提前一天；每次操作产生 $A$ 不愉快度。
② 增加一部分老师负责学科 $Z$，这将导致学科 $Z$ 的出成绩时间提前一天；每次操作产生 $B$ 不愉快度。
上面两种操作中的参数 $X, Y, Z$ 均可任意指定，每种操作均可以执行多次，每次执行时都可以重新指定参数。
现在希望你通过合理的操作，使得最后总的不愉快度之和最小，输出最小的不愉快度之和即可。

输入格式

第一行三个非负整数 $A, B, C$，描述三种不愉快度，详见【题目描述】；
第二行两个正整数 $n, m$，分别表示学生的数量和课程的数量；
第三行 $n$ 个正整数 $t_i$，表示每个学生希望的公布成绩的时间；
第四行 $m$ 个正整数 $b_i$，表示按照原本的计划，每门课程公布成绩的时间。

输出格式

输出一行一个整数，表示最小的不愉快度之和。

输入输出样例

输入 #1

100 100 2
4 5
5 1 2 3
1 1 2 3 3

输出 #1

6

输入 #2

3 5 4
5 6
1 1 4 7 8
2 3 3 1 8 2

输出 #2

33

说明/提示

样例解释 1

由于调整操作产生的不愉快度太大，所以在本例中最好的方案是不进行调整；全部的 $5$ 门课程中，最慢的在第 $3$ 天出成绩；
同学 $1$ 希望在第 $5$ 天或之前出成绩，所以不会产生不愉快度；
同学 $2$ 希望在第 $1$ 天或之前出成绩，产生的不愉快度为 $(3 - 1) \times 2 = 4$；
同学 $3$ 希望在第 $2$ 天或之前出成绩，产生的不愉快度为 $(3 - 2) \times 2 = 2$；
同学 $4$ 希望在第 $3$ 天或之前出成绩，所以不会产生不愉快度；
不愉快度之和为 $4 + 2 = 6$。

数据范围

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

分析

设经过操作后所有成绩全部公布的时间为 $x$，所获得的不愉快度为 $f(x)$。
当 $x$ 很小，那么大部分同学都能在其能忍受的时间 $t_i$ 内知晓成绩，但是由于 $x$ 很小，$b_i>x$ 的情况是很多的，为了使所有科目的成绩都在时间 $x$ 内出来，就需要将大于 $x$ 的 $b_i$ 减小，那么就会因为多次修改 $b_i$ 获得较多的不愉快度，因此 $f(x)$ 是比较大的；当 $x$ 很大，虽然不用怎么修改 $b_i$，但是 $x$ 会超出大部分同学的时限 $t_i$，因此 $f(x)$ 也是比较大的。
根据以上分析，$f(x)$ 应当是一个下凸的单峰函数，可以用三分法找到极小值点。
接下来分析如何计算 $f(x)$的值。假设强制所有成绩全部公布的时间为 $x$，将 $f(x)$ 分为两部分，等待成绩公布获得的不愉快度，以及修改 $b_i$ 使得对于任意 $b_i$ 有 $b_i\le x$ 所获得的不愉快度。等待成绩公布获得的不愉快度可以直接简单累加，res+=C*(x-t[i])。接下来讨论修改 $b_i$ 使得对于任意 $b_i$ 有 $b_i\le x$ 所获得的不愉快度。若 $A>B$ 显然将成绩公布时间大于 $x$ 的课程全部使用操作 $2$ 调整为 $x$ 更优；若 $A<B$ 显然要尽量使用操作 $1$，当公布时间小于 $x$ 的课程全部因操作 $1$ 导致公布时间推迟到 $x$ 时，将剩下公布时间大于 $x$ 的课程使用操作 $2$ 处理。按照以上为规则，即可在 $O(n+m)$ 内得到 $f(x)$。

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#define ll long long
#define N 100003
using namespace std;
int t[N],b[N];
int n,m;
ll A,B,C;
ll f(int x)//出成绩的时间为x
{
	int i;
	ll res=0;
	for(i=1;i<=n;i++)
	{
		if(x>t[i])//到截止日期还没出成绩
		{
			res+=C*(x-t[i]);
		}
	}
	//计算更改截止日期的代价
	if(A<B)
	{
		ll extra,need;
		extra=need=0;
		for(i=1;i<=m;i++)
		{
			if(b[i]<x) extra+=x-b[i];
			else if(b[i]>x) need+=b[i]-x;
		}
		//多余的天数为extra，可以用来弥补超过x的天数need
		/*
			当公布时间小于x的课程全部因操作1导致公布时间推迟到x时
			将剩下公布时间大于x的课程使用操作2处理
		*/
		if(extra>need) res+=A*need;
		else res+=A*extra+(need-extra)*B;
	}
	else//全部使用操作2
	{
		for(i=1;i<=m;i++)
		{
			if(b[i]>x)
			{
				res+=B*(b[i]-x);
			}
		}
	}
	return res;//获得f(x)
}
int main()
{
	cin>>A>>B>>C;
	cin>>n>>m;
	int i;
	for(i=1;i<=n;i++) scanf("%d",t+i);
	for(i=1;i<=m;i++) scanf("%d",b+i);
	int ans;
	/*
		特判
		当C很大，就要让x=min{t[i]}
		不能让任何一个同学等一天
		否则代价巨大
		也不能让x<min{t[i]}
		否则修改b[i]的代价也会变大
	*/
	if(C==10000000000000000)
	{
		ans=0x3f3f3f3f;
		for(i=1;i<=n;i++) ans=min(ans,t[i]);
	}
	else//三分
	{
		int l,r;
		l=r=1;
		for(i=1;i<=n;i++) r=max(r,t[i]);
		while(r-l>=10)//预留的区间为10
		{
			int lmid=l+(r-l)/3;
			int rmid=r-(r-l)/3;
			if(f(lmid)>f(rmid))
			{
				ans=l;
				l=lmid+1;
			}
			else r=rmid-1;
		}
		while(l<=r)
		{
			if(f(l)<f(ans)) ans=l;
			l++;
		}
	}
	cout<<f(ans)<<endl;//输出
	return 0;
}