[SHOI2017]期末考试 木桶效应+贪心

[SHOI2017]

• 首先分析一下本题的模型，可以想象成一个木桶效应

• 最后的答案显然之和最晚结束时间有关
• 因此我们可以枚举结束时间，再贪心地分配人力，就可以求出以这个时间结束的最小不愉快度。 

• 虚线此时是要求改完卷子的时间，那么在虚线右边的时间就需要通过调度老师或者增加老师来弥补。首先判断是否有A≤B，如果是，则虚线左边的空隙都可以拿来填补虚线右边的时间条，剩下的（若A>B，则剩下的就还是原来那么多）需要拿B*天数来弥补。再根据学生的需要，把虚线左边的橙色线条到虚线的距离和都统计出来，乘上C，就是我们把结束时间定在虚线位置的不愉快度。

• 然后60pts就可以直接O(n^2)计算了

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const int N=1e6;
ll t[N],b[N],A,B,C,n,m,top;
ll ans=1e18;
inline ll read(){
	ll num=0;char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))num=num*10+ch-'0',ch=getchar();
	return num;
}
int main()
{
	A=read(),B=read(),C=read(),n=read(),m=read();
	rep(i,1,n)t[i]=read();
	rep(i,1,m)b[i]=read(),top=max(top,b[i]);
	rep(i,1,top){
		ll L=0,R=0,tot=0;
		rep(j,1,m){
			if(b[j]<i)L+=i-b[j];
			if(i<b[j])R+=b[j]-i;
		}
		if(A<=B){
			if(L>=R){
				tot+=R*A;
			}else{
				tot+=L*A+(R-L)*B;
			}
		}else{
			tot+=R*B;
		}
		rep(j,1,n){
			if(t[j]>=i)continue;
			tot+=(i-t[j])*C;
		}
		ans=min(ans,tot);
	}
	cout<<ans;
	return 0;
}

• 观察中间计算贡献的过程，可以用BIT优化到log(n)
• 中间的数字最大会达到n^3级别，所以要使用long long
• 100pts

#include<bits/stdc++.h>
#define rep(i,a,b) for(ll i=(a);i<=(b);i++)
#define per(i,a,b) for(ll i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const ll N=1e6;
ll t[N],tcnt[N],b[N],bcnt[N],SUM,A,B,C,x,n,m,top;
ll ans=1e18,minn=1e18;
inline ll read(){
	ll num=0;char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))num=num*10+ch-'0',ch=getchar();
	return num;
}
inline void Prll(ll x){if(x>9)Prll(x/10);putchar(x%10+'0');}
ll lowbit(ll x){return x&-x;}
void add(ll x,ll v,ll *c)
{while(x<=N/10)c[x]+=v,x+=lowbit(x);}
ll query(ll x,ll *c)
{ll ans=0;while(x)ans+=c[x],x-=lowbit(x);return ans;}
void subtask1(){
	ll i=minn,L=0,R=0,tot=0;
	L=query(i-1,bcnt)*i-query(i-1,b);
	R=(SUM-query(i,b))-(m-query(i,bcnt))*i;
	if(A<=B){
		if(L>=R){
			tot+=R*A;
		}else{
			tot+=L*A+(R-L)*B;
		}
	}else{
		tot+=R*B;
	}
	tot+=(query(i-1,tcnt)*i-query(i-1,t))*C;
	Prll(tot);
}
void subtask2(){
	rep(i,1,top){
		ll L=0,R=0,tot=0;
		L=query(i-1,bcnt)*i-query(i-1,b);
		R=(SUM-query(i,b))-(m-query(i,bcnt))*i;
		
		if(A<=B){
			if(L>=R){
				tot+=R*A;
			}else{
				tot+=L*A+(R-L)*B;
			}
		}else{
			tot+=R*B;
		}
		tot+=(query(i-1,tcnt)*i-query(i-1,t))*C;
		ans=min(ans,tot);
	}
	Prll(ans);
}
int main()
{
	//freopen("a.in","r",stdin);
	A=read(),B=read(),C=read(),n=read(),m=read();
	rep(i,1,n)x=read(),minn=min(minn,x),add(x,x,t),add(x,1,tcnt);
	rep(i,1,m)x=read(),SUM+=x,top=max(top,x),add(x,x,b),add(x,1,bcnt);
	if(C==1e16)subtask1();
	else subtask2();
	return 0;
}