和[LOJ10004]智力大冲浪一样的思路
\(但注意的LOJ10004中复杂度为O(Nt)，肯定会TLE，所以要考虑优化\)
\(注意到每次查找空闲时间的时候都是从t_{i}往前找，复杂度为O(t)\)
\(可以用并查集维护每段连续的被占用的时间，达到O(1)的复杂度，这样总复杂度就可以缩减到O(n)了\)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include<stdio.h> #include<algorithm> using namespace std; struct Homework { int t, w; bool operator < (const Homework &A) const { if (w != A.w) return w > A.w; return t < A.t; } } a[1000010]; int n, v[700010], tot, maxT; int find(int x) { return v[x] == x ? x : v[x] = find(v[x]); } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d%d", &a[i].t, &a[i].w); maxT = maxT < a[i].t ? a[i].t : maxT; } for (int i = 1; i <= maxT; ++i) v[i] = i; sort(a+1, a+n+1); for (int i = 1, u; i <= n; ++i) { u = find(a[i].t); if (u) { v[u] = u-1; tot += a[i].w; } } printf("%d", tot); return 0; } |