Codeforces 854D(前缀和+二分)

发表于 | 分类于 | | + s

Codeforces 854D
题意：有n+1个城市，每个城市都有一个人，他们要去0城市参加活动，一起待k天，然后再回来，你可以提前去也可以延后回去，问 你能不能使所有人一起待k天，可以的话，最小花费是多少？

我们维护两个前缀和数组$l_i, r_i$，分别表示$i$前面的航班可以使得所有人到达0城市的最小费用、$i$后前面的航班可以使得所有人回去的最小费用，计算直接再开个数组记录各个城市的最小值即可。
然后答案可以合并，是$max(l_i+r_j)$，其中$j$是离$d_i+k+1$天最近的航班。
因为有可能回去的$r_i$对应的航班$i$是到达0城市的航班，中途被我continue了(其实其他方法可以避免)，使得单调性被破坏，我们可以进行恢复单调性(看代码注释部分)，所以直接找 离$d_i+k+1$天最近的航班 就是当前最优解。用二分找较为合适，复杂度$O(nlogn)$

Codeforces Submission

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXM = 100000 + 5;
const LL INF = 9223372036854775807; 
struct data {
    int d, f, t, c;
    bool operator < (const data &b) const {
        return d < b.d;
    }
}a[MAXM];
int n, m, k; 
LL l[MAXM], r[MAXM], cost[MAXM];
void clean() {
    for (int i = 0; i <= m + 1; i++) l[i] = r[i] = -1;
}
void solve() {
    clean();
    for (int i = 1; i <= m; i++) scanf("%d%d%d%d", &a[i].d, &a[i].f, &a[i].t, &a[i].c);
    sort(a + 1, a + 1 + m);

    for (int i = 0; i <= m + 1; i++) cost[i] = INF;
    int cnt = 0;
    LL tot = 0;
    for (int i = 1; i <= m; i++) {
        if (a[i].f == 0) continue;//单调性被破坏，但是这里无所谓，因为都能被遍历到
        if (cost[a[i].f] == INF) cnt++, cost[a[i].f] = (LL)a[i].c, tot += (LL)a[i].c; else 
        if (cost[a[i].f] > a[i].c) tot -= cost[a[i].f], cost[a[i].f] = (LL)a[i].c, tot += (LL)a[i].c;
        if (cnt == n) l[i] = tot;
    }

    for (int i = 0; i <= m + 1; i++) cost[i] = INF;
    cnt = 0, tot = 0;
    for (int i = m; i >= 1; i--) {
        if (a[i].t == 0) continue;//单调性被破坏
        if (cost[a[i].t] == INF) cnt++, cost[a[i].t] = (LL)a[i].c, tot += (LL)a[i].c; else 
        if (cost[a[i].t] > a[i].c) tot -= cost[a[i].t], cost[a[i].t] = (LL)a[i].c, tot += (LL)a[i].c;
        if (cnt == n) r[i] = tot;
    }

    for (int i = m - 1; i >= 1; i--) {//恢复单调性
        if (r[i] == -1) r[i] = r[i + 1];
    }

    LL sc = INF;
    for (int i = 1; i <= m; i++) {
        int ans = 0, dd = a[i].d + k + 1, L = i + 1, R = m + 1;
        if (l[i] == -1) continue;
        if (L > R) continue;
        while (L < R) {
            int mid = (L + R) >> 1;
            if (a[mid].d < dd) {
                L = mid + 1;
            } else ans = R = mid;
        }
        if (r[ans] == -1) continue;
        sc = min(sc, l[i] + r[ans]);
    }
    if (sc == INF) printf("-1\n"); else printf("%I64d\n", sc);
}
int main() {
    scanf("%d%d%d", &n, &m, &k), solve();
    return 0;
}
------ 本文结束 ------