UVA1316 Supermarket

简单题？

思路

按 $p_i$ 排序，贪心取，用并查集维护每一天，使用它就让 $fa[x] = x - 1$ 即可

代码

最开始打的 scanf("%d", &n) != EOF 一直 TLE

#include <bits/stdc++.h>
#define fi first
#define se second
using PII = std::pair<int, int>;
const int N = 1e4 + 100;
int n, fa[N], mxt, ans;
PII a[N];
int get(int x){ return x == fa[x] ? x : fa[x] = get(fa[x]); }
int main()
{
    while (std::cin >> n)
    {
        mxt = ans = 0;
        for (int i = 1; i <= n; ++i) scanf("%d %d", &a[i].fi, &a[i].se), mxt = std::max(mxt, a[i].se);
        std::sort(a + 1, a + n + 1, [&](PII x, PII y){ return x.fi > y.fi; });
        for (int i = 0; i <= mxt; ++i) fa[i] = i; 
        for (int i = 1, t; i <= n; ++i) if ((t = get(a[i].se)) > 0)
        {
            ans += a[i].fi;
            fa[t] = t - 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}