bzoj4868 [Shoi2017]期末考试

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4868

【题解】

根据若干观察、推理、理性感知、感性认为可以发现关于结束时间t是个单峰函数。

（废话）若干个一次函数加在一起肯定是个单峰的啊qwq

所以三分就行啦！

如果A>=B那么肯定都用B操作，更优

否则，算出是否能都用A操作完成，不能补B操作即可。

复杂度O(nlogn)

# include <stdio.h>
# include <string.h>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 5e5 + 10;
const int mod = 1e9+7;

# define RG register
# define ST static

int A, B, C;
int n, m, a[M], b[M];

inline ll chk(int t) {
    ll ret = 0;
    if(A >= B) {
        for (int i=1; i<=m; ++i)
            if(b[i] > t) ret = ret + 1ll * B * (b[i] - t);
        for (int i=1; i<=n; ++i)
            if(t > a[i]) ret = ret + 1ll * C * (t - a[i]); 
        return ret;
    } else {
        ll more = 0, less = 0;    
        for (int i=1; i<=m; ++i) {
            if(b[i] > t) more += b[i]-t;
            if(b[i] < t) less += t-b[i];
        }
        if(more <= less) ret = ret + more * A;
        else ret = ret + less * A + (more-less) * B;
        for (int i=1; i<=n; ++i)
            if(t > a[i]) ret = ret + 1ll * C * (t - a[i]); 
        return ret;
    }
}
int main() {
    scanf("%d%d%d", &A, &B, &C); 
    scanf("%d%d", &n, &m); 
    for (int i=1; i<=n; ++i) scanf("%d", a+i);
    for (int i=1; i<=m; ++i) scanf("%d", b+i);
    
    int l = 1, r = 1e5;
    ll ans = 1e18;
    while(1) {
        if(r-l<=10) {
            for (int i=l; i<=r; ++i)
                ans = min(ans, chk(i));
            break;
        }
        int mid1 = l + (r-l)/3, mid2 = r - (r-l)/3;
        if(chk(mid1) < chk(mid2)) r = mid2;
        else l = mid1;
    }
    printf("%lld
", ans); 
     
    return 0;
}