BZOJ-4868: [Shoi2017]期末考试

[文章目录]

Description

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

我们发现决定学生是否需要多等只取决于时间最长的哪一科。所以我们对于AB操作后的最长的时间考虑,这个时间变短时,AB操作会变大,C操作代价变小。反之,AB操作变小,C变大。所以和代价是一个单峰函数。我们三分(可惜我省选那天根本不TMD会三分啊!!!),三分其实是分三舍一,其实也挺简单的。

对于一个单峰函数,我们要找极值,所以分成三段,mid1=l+(r-l)/3,mid2=r-(r-l)/3,如果mid1>mid2说明一段[l,mid1]||[mid2,r]中肯定是无解的。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll ;
ll A,B,C;
int n,m,mx=-1<<30;
int t[101000],b[101000];
ll sumt,ans=0x7f7f7f7f7f7f7f7f;
ll calc(int x)
{
	ll re=0,sum1=0,sum2=0;
	for(int i=1;i<=n;i++)
		if(t[i]<x) re+=(x-t[i]);
	re*=C;
	for(int i=1;i<=m;i++)
		if(b[i]>x) sum1+=(b[i]-x);
		else sum2+=(x-b[i]);
	if(A>=B) re+=sum1*B;
	else if(sum1<=sum2) re+=sum1*A;
	else re+=(sum2*A+(sum1-sum2)*B);
	return re;
}
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]),mx=max(mx,b[i]);
	if(C>10000000000ll)
	{
		int mi=1<<30;
		for(int i=1;i<=n;i++) mi=min(mi,t[i]);
		printf("%lld",calc(mi));
		return 0;
	}
	int l=0,r=mx+1,mid1,mid2;
	while(1)
	{
		if(r-l<=6)
		{
			for(int i=l;i<=r;i++) ans=min(ans,calc(i));
			break;
		}
		mid1=l+(r-l)/3,mid2=r-(r-l)/3;
		if(calc(mid1)<calc(mid2)) r=mid2;
		else l=mid1;
	}
	printf("%lld",ans);
	return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注