刷题记录:牛客NC20439[SHOI2017]期末考试

传送门:牛客

题目描述:

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

首先对于这道题的正解应该是三分,但是因为我对于三分并不是很熟练,且这个单峰函数并不是很好推,所以我选择了一种暴力的思想

牛客网上难度三星,洛谷紫题,所实话对于三分来讲牛客应该四星,对于暴力来讲三星也马马虎虎

对于这种题目,我们刚读完应该都会有一种挺显然的想法,我们可以直接枚举最后一门成绩公布的日期,因为每一个同学所想要的是全部课程的公布,所以对于我们最终答案的影响只有最后一门科目的公布时间.当我们得出了这个想法之后,我们考虑我们能进行的操作,发现当A>=B时,显然我们直接采用B是最优的(因为同样是将一门科目提前一天,但是A是有副作用的),当A

接下来是这道题的暴力解法的难点,我们怎么判断有哪些课程是可以使用A的,并且我们还需要知道对于每一次我们枚举出来的最后期限对于我们的同学来说,有哪些同学是不满的,是需要加不愉快度的,显然以上我们需要得到肯定不能够每一次都进行枚举的,这样肯定是会超时的,此时我们有一种桶排的想法,我们直接按照时间样同学期待与课程发布时间都装入桶中,并且对于这些时间我们都求一个和,以及求同学的总人数,我们思考一下假设我们此时枚举到的最后期限是K,那么对于我们大于K之后的同学来说,此时这些同学是不增加不愉快度的,并且我们在之前就求出了总时间,因此我们只要减去这些同学剩下的显然就是增加愉快度的那一批人的总时间,有人可能就会发问了,即使我们得到了这个有什么用呢,我们发现拿剩下的同学人数Sum,Sum*K-总时间,得到的就是每一个同学的不满意度了,因为对于每一个同学来说最后都是要到K位置的.类似的,使用这种类前缀和的思想我们也可以计算出每一门科目需要提前的时间以及总共可以推迟的科目的时间

注意点:需要开Unsigned longlong,longlong不够大

代码需要管理和记录的变量较多,比较混乱,容易搞混,请耐心.

具体代码:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef unsigned long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
ll A,B,C;
ll m,n;
ll t[maxn],b[maxn];
ll sum[maxn];
ll sum_b[maxn];
ll sum_t[maxn];
int main() {
	scanf("%lld%lld%lld",&A,&B,&C);
	scanf("%lld%lld",&n,&m);
	ll leiji_shijian=0;ll leiji_renshu=0;ll leiji_shijian2=0,leiji_renshu2=0;ll zongshijian=0;
	sum[0]=0;
	ll maxx2=0;ll zongrenshu=0;
	for(int i=1;i<=n;i++){
		t[i]=read();
		leiji_shijian+=t[i];
		leiji_renshu+=1;
		sum_t[t[i]]++;
		maxx2=max(maxx2,t[i]);
	} 
	ll maxx=0;
	for(int i=1;i<=m;i++){
		b[i]=read();
		sum_b[b[i]]++;
		zongshijian+=b[i];
		zongrenshu+=1;
		maxx=max(maxx,b[i]);
	} 
	ll ans=ll_maxn;
	if(maxx2>maxx) {
		for(int i=maxx2;i>maxx;i--) {
			leiji_shijian-=(i*sum_t[i]);
			leiji_renshu-=sum_t[i];
		}
	}
	for(int i=maxx;i>=1;i--) {
		leiji_shijian-=(i*sum_t[i]);//记录同学们对于此刻的不满度总和
		leiji_renshu-=sum_t[i];//记录不满的同学的总人数
		leiji_shijian2+=(i*sum_b[i]);//记录需要调整的课程的总时间
		leiji_renshu2+=sum_b[i];//记录需要调整的课程数
		if(A>=B) {
			ll ans1=(leiji_shijian2-leiji_renshu2*i)*B;
			ans1+=(leiji_renshu*i-leiji_shijian)*C;
			ans=min(ans1,ans);
		}else {
			ll ans1=(leiji_shijian2-leiji_renshu2*i);
			ll ketiaozheng=(i*(zongrenshu-leiji_renshu2))-(zongshijian-leiji_shijian2);
			if(ketiaozheng>ans1) {
				ans1=ans1*A;
				ans1+=(leiji_renshu*i-leiji_shijian)*C;
				ans=min(ans1,ans);
			}else {
				ans1=ketiaozheng*A+(ans1-ketiaozheng)*B;
				ans1+=(leiji_renshu*i-leiji_shijian)*C;
				ans=min(ans1,ans);
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}