题解 P1314 【聪明的质监员】

彼岸归航 · 2018-10-22 17:34:31 · 题解

因为求的是差值，所以肯定中间小两边大，马上就能想到三分。（表示想了很久才明白为什么可以二分）虽然说是三分但复杂度和二分差不多的，无非就是常数大一点（什么）。

首先我们想到把l设为min\ w[i]，r设为max\ w[i]。开心地写出代码，通过了样例，然后震惊地发现全WA了，以下是爆零部分代码。

while(l + 3 < r) {
    int mid = (l + r) >> 1; 
    int midl = mid - 1; 
    int midr = mid + 1; 
    ll k1 = check(midl); 
    ll k2 = check(midr); 
    if(k1 < k2) res = min(res, k1), r = midr; 
    else res = min(res, k2), l = midl; 
}
for(int i = l; i <= r; i++) res = min(res, check(i)); 

这个时候肯定要问，为什么WA掉了？

上面这种做法有一个漏洞，枚举w的时候并不是每一个w都能作为断点，也就是说，可能会搞出来两个等价的w，这时你并不能判断答案到底在左边还是右边。
所以要对枚举的w去重。（应该是这个意思）我们只要从小到大枚举每一个不一样的w[i]就可以了。那么只要排一遍序就可以了。

AC代码：

#include<bits/stdc++.h>

using std::max; 
using std::sort; 

typedef long long ll; 

const int N = 200000; 

struct ele {
    ll w, v; 
    void read() {
        scanf("%lld %lld", &w, &v); 
    }
}; 
struct seg {
    int l, r; 
    void read() {
        scanf("%d %d", &l, &r); 
    }
}; 

int n, m; 
ll  S; 
ele a[N + 3]; 
seg b[N + 3]; 

int l, r; 
ll res = -1; 
ll s[N + 3]; 
ll x[N + 3]; 
ele c[N + 3]; 
ll d[N + 3]; 

ll abs(ll a) {
    return a < 0 ? -a : a; 
}
ll min(ll a, ll b) {
    if(a == -1) return b; 
    if(b == -1) return b; 
    return a < b ? a : b; 
}

bool cmp(ele a, ele b) {
    return a.w < b.w; 
}

ll check(int w) {
    for(int i = 1; i <= n; i++) {
        if(a[i].w >= w) s[i] = s[i - 1] + a[i].v, x[i] = x[i - 1] + 1; 
        else s[i] = s[i - 1], x[i] = x[i - 1]; 
    }
    ll ans = 0; 
    for(int i = 1; i <= m; i++) ans += (x[b[i].r] - x[b[i].l - 1]) * (s[b[i].r] - s[b[i].l - 1]); 
    return abs(ans - S); 
}

int main() {
    scanf("%d %d %lld", &n, &m, &S); 
    for(int i = 1; i <= n; i++) a[i].read(), c[i] = a[i]; 
    for(int i = 1; i <= m; i++) b[i].read(); 

    sort(c + 1, c + n + 1, cmp); 
    for(int i = 1; i <= n; i++) {
        if(c[i].w == c[i - 1].w) continue; 
        else d[r++] = c[i].w; 
    }
    l = 1; 

    while(l + 3 < r) {
        int mid = (l + r) >> 1; 
        int midl = mid - 1; 
        int midr = mid + 1; 
        ll k1 = check(d[midl]); 
        ll k2 = check(d[midr]); 
        if(k1 < k2) res = min(res, k1), r = midr; 
        else res = min(res, k2), l = midl; 
    }
    for(int i = l; i <= r; i++) res = min(res, check(d[i])); 

    printf("%lld\n", res); 

    return 0; 
}