关键词：
http://www.lydsy.com/JudgeOnline/problem.php?id=4868
题目复制于洛谷：https://www.luogu.org/problemnew/show/P3745#sub
有n位同学，每位同学都参加了全部的m门课程的期末考试，都在焦急的等待成绩的公布。
第i位同学希望在第ti天或之前得知所有课程的成绩。如果在第ti天，有至少一门课程的成绩没有公布，他就会等待最后公布成绩的课程公布成绩，每等待一天就会产生C不愉快度。对于第i门课程，按照原本的计划，会在第bi天公布成绩。
有如下两种操作可以调整公布成绩的时间：
1.将负责课程X的部分老师调整到课程Y，调整之后公布课程X成绩的时间推迟一天，公布课程Y成绩的时间提前一天；每次操作产生A不愉快度。
2.增加一部分老师负责学科Z，这将导致学科Z的出成绩时间提前一天；每次操作产生B不愉快度。
上面两种操作中的参数X;Y;Z均可任意指定，每种操作均可以执行多次，每次执行时都可以重新指定参数。
现在希望你通过合理的操作，使得最后总的不愉快度之和最小，输出最小的不愉快度之和即可。
感觉像三分最终出成绩的时间但是不知道怎么证明于是看了题解。
首先我们考虑如果我们知道最终发成绩的时间的话，那么我们显然能得到此时的唯一最优解。
无脑做法：
显然学生代价C我们立刻能求出来，O(n)无脑。
然后我们考虑AB代价，显然B的操作要比A优秀，所以当B<=A时显然只需要B操作即可。
而且B操作代价求法很无脑，一个O(m)就能求。
考虑A操作，先预处理排好序然后无脑加减就可以做到一个O(m)。
所以综上固定时间求代价的复杂度为O(max(n,m))，且nm数量级一致，简记做O(n)。
再考虑对于学生来说，显然时间越小代价越小。
对于老师来说，显然时间越大代价越大。
复合函数显然满足单峰性，可以三分，是一个log的。
所以是O(nlogn)，1e5绝对能过。
（我的代码就是这个）
跑得快做法：
见http://www.cnblogs.com/RabbitHu/p/LOJ2141.html提供了一种O(n)求最优解的方法。
#include<cstdio> #include<cctype> #include<algorithm> using namespace std; typedef long long ll; const int N=1e5+5; inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } ll A,B,C; int n,m,t[N],b[N],nb[N]; inline ll suan(int ed){ ll ans=0; for(int i=1;i<=n;i++){ if(t[i]<ed)ans+=(ed-t[i])*C; else break; } for(int i=1;i<=m;i++)nb[i]=b[i]; if(A<B){ int l=1,r=m; while(l<r){ if(nb[r]>ed){ int delta=ed-nb[l]; if(delta<0)break; if(nb[r]-delta>ed){ nb[r]-=delta; nb[l++]=ed; ans+=A*delta; }else{ ans+=A*(nb[r]-ed); nb[l]+=nb[r]-ed; nb[r--]=ed; } }else break; } } for(int i=m;i>=1;i--){ if(nb[i]>ed)ans+=(nb[i]-ed)*B; } return ans; } ll sanfen(int l,int r){ while(233){ if(r-l<3){ ll ans=suan(r); for(int i=l;i<r;i++)ans=min(ans,suan(i)); return ans; } int mid1=l+(r-l)/3,mid2=mid1+(r-l)/3; if(suan(mid1)>suan(mid2))l=mid1; else r=mid2; } } int main(){ A=read(),B=read(),C=read(); n=read(),m=read(); for(int i=1;i<=n;i++)t[i]=read(); for(int i=1;i<=m;i++)b[i]=read(); sort(t+1,t+n+1);sort(b+1,b+m+1); printf("%lld\n",sanfen(t[1],max(t[n],b[m]))); return 0; }
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++
bzoj4868[shoi2017]期末考试——三分枚举
考场上xjb三分过掉了。然后$sdfzyhx$、$silvernebula$$O(n)$虐掉了。我还是太菜了#include<cstdio>#include<cmath>#include<queue>#include<cstring>#include<iostream>#include<algorithm>usingnames 查看详情
bzoj4868:[shoi2017]期末考试
Description有n位同学，每位同学都参加了全部的m门课程的期末考试，都在焦急的等待成绩的公布。第i位同学希望在第ti天或之前得知所.有.课程的成绩。如果在第ti天，有至少一门课程的成绩没有公布，他就会等待最后公布成绩的... 查看详情
bzoj4868[shoi2017]期末考试
Description有n位同学，每位同学都参加了全部的m门课程的期末考试，都在焦急的等待成绩的公布。第i位同学希望在第ti天或之前得知所.有.课程的成绩。如果在第ti天，有至少一门课程的成绩没有公布，他就会等待最后公布成绩的... 查看详情
bzoj4868[shoi2017]期末考试前缀和
题目描述有n位同学，每位同学都参加了全部的m门课程的期末考试，都在焦急的等待成绩的公布。第i位同学希望在第ti天或之前得知所.有.课程的成绩。如果在第ti天，有至少一门课程的成绩没有公布，他就会等待最后公布成绩的... 查看详情
[bzoj4868][shoi&sxoi2017]期末考试（贪心）
Description有n位同学，每位同学都参加了全部的m门课程的期末考试，都在焦急的等待成绩的公布。第i位同学希望在第ti天或之前得知所.有.课程的成绩。如果在第ti天，有至少一门课程的成绩没有公布，他就会等待最后公布成绩的... 查看详情
[bzoj4868][六省联考2017]期末考试(三分)
4868:[Shoi2017]期末考试TimeLimit:20Sec MemoryLimit:512MBSubmit:964 Solved:439[Submit][Status][Discuss]Description有n位同学，每位同学都参加了全部的m门课程的期末考试，都在焦急的等待成绩的公布。第i位同学希望在第ti天或之前得知... 查看详情
bzoj4868
4868:[Shoi2017]期末考试TimeLimit: 20Sec MemoryLimit: 512MBSubmit: 892 Solved: 404[Submit][Status][Discuss]Description有n位同学，每位同学都参加了全部的m门课程的期末考试，都在焦急的等待成绩的公布。第i位同学 查看详情
三分bzoj4868[sxoi2017]期末考试
4868:[Sxoi2017]期末考试TimeLimit:20Sec MemoryLimit:512MBSubmit:605 Solved:270[Submit][Status][Discuss]Description有n位同学，每位同学都参加了全部的m门课程的期末考试，都在焦急的等待成绩的公布。第i位同学希望在第ti天或之前得知... 查看详情
bzoj4868期末考试[三分][贪心]
期末考试TimeLimit:20Sec MemoryLimit:512MB[Submit][Status][Discuss]Description Input Output SampleInput 1001002 45 5123 11233SampleOutput 6HINT Solution 首先，由于学生需要知道所有的成绩，这意味着即使只有一个... 查看详情
bzoj4868期末考试
我还第一次见到省选考三分……？#include<bits/stdc++.h>#defineN200005usingnamespacestd;typedeflonglongll;intn,m,r,t[N],b[N];lla,B,c,ans;llcalc(intp){llx=0,y=0;for(inti=1;i<=m;i++)if(b[i]<p)x+=p-b[i];elsey+ 查看详情
bzoj4868期末考试（整数三分）
题意：有n位同学，每位同学都参加了全部的m门课程的期末考试，都在焦急的等待成绩的公布。第i位同学希望在第ti天或之前得知所.有.课程的成绩。如果在第ti天，有至少一门课程的成绩没有公布，他就会等待最后公布成绩的课... 查看详情
2017[六省联考]t1期末考试
4868:[Shoi2017]期末考试TimeLimit: 20Sec MemoryLimit: 512MBSubmit: 842 Solved: 385[Submit][Status][Discuss]Description 有n位同学，每位同学都参加了全部的m门课程的期末考试，都在焦急的等 查看详情
[六省联考2017]期末考试
4868:[Shoi2017]期末考试2017-09-03Description有n位同学，每位同学都参加了全部的m门课程的期末考试，都在焦急的等待成绩的公布。第i位同学希望在第ti天或之前得知所.有.课程的成绩。如果在第ti天，有至少一门课程的成绩没有公布，... 查看详情
loj#2141.「shoi2017」期末考试
题目链接LOJ#2141题解据说这道题可以三分（甚至二分）？反正我是枚举的==先将t和b数组排序后计算出前缀和，然后枚举最晚的出成绩时间，每次可以O(1)直接计算调整到该时间所需的代价。如何计算？对于学生不满意造成的代价... 查看详情
shoi2017试题泛做
一口气做完六个省的省选（误）Day1[Shoi2017]期末考试枚举最大的天数，然后代价贪心地O(1)计算。1#include<cstdio>2#include<algorithm>34#defineRregister5typedeflonglongll;6#definemaxn1000107#definecmax(_a,_b)(_a<(_b)?_a=(_b):0)8 查看详情
2018.4.5shoi2017题集(代码片段)
这三道题分别对应bzoj4868~4870，pdf没法往这放，因此放弃了。T1：方法1（正解）：三分法考虑暴力枚举最晚公布的时间x，关注到2操作是没有负面影响的1操作，所以如果A大于B，那么只需用2操作就可以了，否则先用1操作，不能用1... 查看详情
bzoj4871:[shoi2017]摧毁“树状图”
4871:[Shoi2017]摧毁“树状图”TimeLimit:25Sec MemoryLimit:512MBSubmit:53 Solved:9[Submit][Status][Discuss]Description自从上次神刀手帮助蚯蚓国增添了上千万人口（蚯口？），蚯蚓国发展得越来越繁荣了！最近，他们在地下... 查看详情
bzoj4869[shoi2017]相逢是问候(代码片段)
4869:[Shoi2017]相逢是问候TimeLimit: 40Sec MemoryLimit: 512MBSubmit: 1311 Solved: 470[Submit][Status][Discuss]DescriptionInformatikverbindetdichundmich.信息将你我连结。B君希望 查看详情