题解 P3745 【[六省联考2017]期末考试】

· · 题解

一道比较清真友好的贪心+枚举题qwq

可以发现答案之和公布时间最晚的学科有关，假设其公布时间为k，那么答案为：

\sum \max( 0, k-b_i)*\rm C

但是由于存在两个操作，所以最晚公布的学科的时间是可以被修改的，我们考虑枚举这个最晚公布的学科的时间。

对于一个固定的k，有所有人等待的时间便是一个定值，于是接下来的工作就是如何在消费最小的情况下将所有学科的公布时间改为k

对于\rm A>B的情况，显然最优的方法是全部选\rm B操作，于是我们只需要统计一下对于某一个k，比k大的数与k的差值之和，这个可以比较简单的利用前缀和解决

对于\rm A < B的情况，我们显然要尽量用操作1，不能用的时候再用2.，可以考虑操作1可以被使用的次数，可以发现是比k小的数与k的差之和，同样可以一个前缀和带走，对于剩下的，全部选2.即可

然后就没了...（大雾

Code: 
#include<bits/stdc++.h>
using namespace std ;
#define drep( i, s, t ) for( register int i = t; i >= s; -- i )
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define re register
#define int long long
int gi() {
    char cc = getchar() ; int cn = 0, flus = 1 ;
    while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
    while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
    return cn * flus ;
}
const int N = 1e5 + 5 ; 
int A, B, C, n, m, Max, t[N], b[N], Sum[N], Pre[N], Nxt[N], Sz[N], Rev[N], Siz[N] ; 
int Ans ; 
signed main()
{
    A = gi(), B = gi(), C = gi(), n = gi(), m = gi() ; 
    rep( i, 1, n ) t[i] = gi(), Max = max( Max, t[i] ), ++ Siz[t[i]] ;
    rep( i, 1, m ) b[i] = gi(), Max = max( Max, b[i] ), ++ Sz[b[i]], ++ Rev[b[i]] ;
    sort( t + 1, t + n + 1 ), sort( b + 1, b + n + 1 ) ;
    rep( i, 1, Max ) Siz[i] += Siz[i - 1], Sum[i] = Sum[i - 1] + Siz[i - 1] ; 
    rep( i, 1, Max ) Pre[i] = Pre[i - 1] + Sz[i - 1], Sz[i] += Sz[i - 1] ;
    drep( i, 1, Max ) Nxt[i] = Nxt[i + 1] + Rev[i + 1], Rev[i] += Rev[i + 1] ;
    rep( i, 1, Max ) {
        int rAns = C * Sum[i] ;
        if( rAns > Ans && Ans ) break ; 
        if( A < B ) rAns += min( Pre[i], Nxt[i] ) * A, Nxt[i] -= Pre[i], rAns += max( 0ll, Nxt[i] ) * B ; 
        else rAns += Nxt[i] * B ;
        if( !Ans || rAns < Ans ) Ans = rAns ; 
    }
    printf("%lld\n", Ans ) ;
    return 0 ;
}