题解:洛谷P3745 期末考试(整数三分)
题目大意:给出 \(n\) 个同学期望出成绩的时间限制 \(a_i\) 和 \(m\) 个学科公布成绩的初始时间 \(t_i\) ,1个同学每多等一天就产生 A 的不愉快度。问通过一番操作后最小的不愉快度之和是多少?
操作有两种:
1.让学科 X 的发布时间晚1天,学科 Y 的发布时间早1天,产生A的不愉快度。
2.让学科 Z 的发布时间早1天,产生 B 的不愉快度。
思路:
设 \(t\) 表示规定的所有学科公布成绩的时间期限,\(y\) 表示满足第 \(t\) 天时出所有成绩的最小不愉快度之和。
则 \(y\) 关于 \(t\) 的函数是一个下凹函数(或者说形状类似一个开口向上的抛物线吧)
考虑三分出最低点(三分的部分就是板子了)
考虑怎么算 \(y\) ,由两部分组成:(1)\(t_i<t\) 的所有同学的不愉快度 \(res\)(2)操作的不愉快度
操作的不愉快度有两种,一种是 A 的移大补小,一种是 B 的暴力删。
首先明确一点:不关心大的到底补到了哪个小的,小的最终具体时间也不关心,因为同学的不愉快度只跟上限 \(t\) 有关。下面对操作的不愉快度进行分讨:
(1)若 \(B \leq A\) , 那肯定只使用 B
(2)若 \(A < B\) , 记所有小于 t 的学科的时间可以提供的补过来的空缺为 val1 , 大于 t 的学科超过 t 的总时间为 val2
当 \(val1 \geq val2\),全用 A 操作
当 \(val1 < val2\),进行 val1 次 A 操作,再进行 (val2-val1)次 B 操作
注意三分的边界和退出条件,算 \(res,val1,val2\) 时可以 \(O(N)\) 遍历 \(a_i\) 和 \(t_i\) ,也可以先排序后记个前缀和,三分的时候二分查找一下 分界点 \(t\) 再两个数组中的位置,时间复杂度 \(O(log_3N*log_2N)\)(感觉有点抽象,具体细节看代码吧~),注意特判C很大的情况,不然要开unsigned long long。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define F(i,l,r) for(int i=l;i<=r;++i)
const int N=1e5+5;
const ll M=1e16;
int n,m,A,B,a[N],t[N];
ll C,s1[N],s2[N];
inline ll suan(int x){//限制所有学科天数不超过x
ll w1=upper_bound(t+1,t+m+1,x)-t-1,w2=lower_bound(a+1,a+n+1,x)-a-1,
val1=x*w1-s2[w1],val2=(s2[m]-s2[w1])-(m-w1)*x,
res=(w2*x-s1[w2])*C;
//val1:<x的w1天里有多少空缺
//val2:超过x天的学科里要移动多少天过来(或者说理论上要多少空缺)
if(A<B){
if(val1>=val2) return A*val2+res;
else return A*val1+B*(val2-val1)+res;
}
return val2*B+res;
}
int main(){
scanf("%d%d%lld%d%d",&A,&B,&C,&n,&m);
F(i,1,n) scanf("%d",&a[i]); sort(a+1,a+n+1); F(i,1,n) s1[i]=s1[i-1]+a[i];
F(i,1,m) scanf("%d",&t[i]); sort(t+1,t+m+1); F(i,1,m) s2[i]=s2[i-1]+t[i];
if(C==1e16) return printf("%lld",suan(a[1])),0;//特判C很大的情况,不然要开unsigned long long
int l=0,r=t[m]+1,mid1,mid2;
while(l+2<r){
mid1=(2*l+r)/3,mid2=(l+2*r)/3;
if(suan(mid1)>=suan(mid2)) l=mid1;
else r=mid2;
}
printf("%lld",min({suan(l),suan(r),suan(l+1)}));
return 0;
}
标签:洛谷,suan,题解,long,return,愉快,val2,P3745,val1
From: https://www.cnblogs.com/superl61/p/17801230.html