CodeForces 853 B Jury Meeting

思维题，老实说我并没有想出来，应该说是我想歪了……

看了一个大佬的代码，真的是超整洁，这是我目前见过最整洁的代码。值得借鉴。

题意：
每个点距源点有几条单项路径，路径有个花费和另一个时间。要你买构造来回路径使得中间间隔时间不小于 k 。

思路：
首先按照日期排序，菜鸡第一想到的是按照花费权值排序
在相同日期的路径中找出所有花费权值最小的加入集合并维护其最小。如果集合已满就记录当前日期的花费。
一个道理在正向前往目的地来一次，反向返回来一次。
就得到了当前日期正向的的最小值，当前日期反向返回的最小值。
再正向找出当前日期之前的最小值，当前日期之后返回的最小值，使得中间区间尽可能大，越往中间花费越小。

再枚举间隔区间，将往返花费相加找出最小值就是答案。

AC Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxd = 1e6 + 5;
const int maxn = 1e5 + 5;

int n, m, k;
int fIn[maxn], fOut[maxn];
ll minInCost[maxd], minOutCost[maxd];
ll prefix[maxd], suffix[maxd];

struct Item {
    int d, f, t, c;
    bool operator<(const Item& item) const { return d < item.d; }
} items[maxn];

int main()
{
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < m; i++) {
        Item& item = items[i];
        scanf("%d %d %d %d", &item.d, &item.f, &item.t, &item.c);
    }

    sort(items, items + m);

    ll total = 0;
    int cnt = 0;
    for (int i = 0; i < m;) {
        int d = items[i].d;
        for (; i < m; i++) {
            Item& item = items[i];
            if (item.d != d)
                break;
            if (item.f == 0)
                continue;
            if (!fIn[item.f]) {
                cnt++;
                fIn[item.f] = item.c;
                total += item.c;
            } else if (item.c < fIn[item.f]) {
                total -= fIn[item.f] - item.c;
                fIn[item.f] = item.c;
            }
        }
        if (cnt == n)
            minInCost[d] = total;
    }

    cnt = total = 0;
    for (int i = m - 1; i >= 0;) {
        int d = items[i].d;
        for (; i >= 0; i--) {
            Item& item = items[i];
            if (item.d != d)
                break;
            if (item.t == 0)
                continue;
            if (!fOut[item.t]) {
                cnt++;
                fOut[item.t] = item.c;
                total += item.c;
            } else if (item.c < fOut[item.t]) {
                total -= fOut[item.t] - item.c;
                fOut[item.t] = item.c;
            }
        }
        if (cnt == n)
            minOutCost[d] = total;
    }

    int D = items[m - 1].d;

    for (int i = 1; i <= D; i++) {
        prefix[i] = prefix[i - 1];
        if (minInCost[i])
            prefix[i] = prefix[i] ? min(prefix[i], minInCost[i]) : minInCost[i];
    }

    for (int i = D; i > 0; i--) {
        suffix[i] = suffix[i + 1];
        if (minOutCost[i])
            suffix[i] = suffix[i] ? min(suffix[i], minOutCost[i]) : minOutCost[i];
    }

    ll ans = -1;
    for (int i = 1; i + k + 1 <= D; i++) {
        if (prefix[i] && suffix[i + k + 1]) {
            ll res = prefix[i] + suffix[i + k + 1];
            ans = ans != -1 ? min(ans, res) : res;
        }
    }
    printf("%lld\n", ans);
    return 0;
}