洛谷 P3745 【六省联考2017】期末考试 题解

洛谷 P3745 【六省联考2017】期末考试 题解

2020-2-25 xiaoh

题意

有$n$个学生,$m$门科目的考试($1\leq n,m\leq 10^5$).第$i$个学生希望所有成绩在$t_i$天前出来,在此之后每晚一天会有$C$的不满意值($1\leq C\leq 10^{18}$).第$i$门科目的成绩出来的时间为$b_i$.我们可以对一些科目进行如下两种操作:
1.将科目$x$提前$1$天,并将科目$y$延迟$1$天,会有$A$的不满意值.
2.将科目$x$提前$1$天,会有$B$的不满意值.($1\leq A,B\leq 10^{18}$)
每种操作可以进行任意多次,求最小的不满意值.

题解

显然,学生的不满意值只会随着最晚出来的那一科的时间而决定.我们可以考虑枚举最晚那一科出成绩的时间,学生的总不满意值可以通过$O(1)$递推,且是单调不下降的.且教师的总不满意值也可以通过$O(1)$递推,且是单调不上升的.对于需要将最晚的出成绩时间往前调,若$A>B$则显然全部使用操作$2$更优,否则能用操作$1$就用操作$1$,其余的全部用操作$2$即可.时间复杂度的瓶颈在于对$b$和$t$排序,时间复杂度$O(n\log n+m\log m)$.注意有个坑点在于使用long long是不够的,会WA掉两个点,要用__int128才行(题解中有unsigned long long就能过,不过我没试过,大家可以自己试试QAQ).

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=100010;
const __int128 inf=(__int128)LONG_LONG_MAX*(__int128)LONG_LONG_MAX;
__int128 p,q,r;
int n,m;
int t[MAXN],b[MAXN];
__int128 ans=inf;
int main()
{
    read(p),read(q),read(r);
    p=min(p,q);
    read(n),read(m);
    for(int i=1;i<=n;i++) read(t[i]);
    for(int i=1;i<=m;i++) read(b[i]);
    sort(t+1,t+n+1),sort(b+1,b+m+1);
    __int128 num1=0,num2=0,sumpre=0,sum2=0,sumsuf=0;
    for(int i=b[m];i>=1;i--)
    {
        sumsuf=sumsuf+num1;
        while(b[m-num1]==i) num1++;
    }
    num1=0;
    for(int i=1;i<=max(t[n],b[m]);i++)
    {
        sum2+=num2*r,sumpre+=num1;
        while(t[num2+1]==i&&num2<=n) num2++;
        while(b[num1+1]==i&&num1<=m) num1++;
        if(sumpre>=sumsuf) ans=min(ans,sumsuf*p+sum2);
        else ans=min(ans,sumpre*p+(sumsuf-sumpre)*q+sum2);
        sumsuf-=(m-num1);
    }
    write(ans),putchar('\n');
	return 0;
}