【洛谷3745】[六省联考2017] 期末考试（水题）

点此看题面

• 有(n)个人，每个人都报考了全部(m)门学科。第(i)个人有个预期日(t_i)，所有成绩全部公布的日子每迟于(t_i)一天，就需要花费(C)点代价。
• 每门学科有个初始成绩公布时间(b_i)，你可以任意次花费(A)点代价( exttt{++}b_i, exttt{--}b_j)，还可以任意次花费(B)点代价( exttt{++}b_i)。
• 求最小代价。
• (n,m,t_i,b_ile10^5)

暴力枚举最终时间

非常水的一道题。。。

直接暴枚最终时间(i)，那么对于所有(t_j>i)的人会产生(sum_{t_j>i}(t_j-i) imes C)的代价。

而我们要把最终时间调整到不迟于(i)，首先如果(A>B)，肯定直接把所有(b_k>i)的学科共花费(sum_{b_k>i}(b_k-i) imes B)的代价变成(i)，否则可以先花费(min{sum_{b_k<i}(i-b_k),sum_{b_k>i}(b_k-i)} imes A)的代价尽可能利用第一种操作修改，然后剩余部分再用第二种操作修改。

具体实现过程中，只需要维护(sum_{t_j>i}(t_j-i) imes C,sum_{b_k<i}(i-b_k),sum_{b_k>i}(b_k-i))三个量，那么就只要在(i)增大的时候单调移动(j,k)两个指针即可。

代码：(O(V))

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define LL long long
using namespace std;
int n,m,A,B,C,t[N+5],b[N+5];
namespace FastIO
{
	#define FS 100000
	#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
	char oc,FI[FS],*FA=FI,*FB=FI;
	Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
	Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
}using namespace FastIO;
int main()
{
	RI i;for(read(A,B,C,n,m),i=1;i<=n;++i) read(t[i]);for(i=1;i<=m;++i) read(b[i]);
	LL ts=0,f1=0,f2=0;for(sort(t+1,t+n+1),sort(b+1,b+m+1),i=1;i<=m;++i) f2+=b[i];//初始只有f2=∑b
	RI j=1,k=1;LL ans=1e18;for(i=0;i<=N;ts+=j-1,f1+=k-1,f2-=m-k+1,++i)//根据三式中的项数，更新三个和的值
		{W(j<=n&&t[j]==i) ++j;W(k<=m&&b[k]==i) ++k;ans=min(ans,ts*C+(A>B?f2*B:min(f1,f2)*A+(f2-min(f1,f2))*B));}//单调移动j,k；更新ans
	return printf("%lld
",ans),0;
}