yaoxi-std 的博客

$\text{开}\mathop{\text{卷}}\limits^{ju\check{a}n}\text{有益}$

0%

P8272 [USACO22OPEN] Apple Caching G

发表于 更新于 分类于

P8272 [USACO22OPEN] Apple Caching G

题面

题目链接

解法

看完样例，不难发现一头奶牛能够接到的苹果的区域如下图所示。

（横坐标为位置，纵坐标为时间，区域就是两条直线上方部分的半平面交）

img1

假设第 $i$ 群奶牛能够接到的苹果集合为 $S_i$。

考虑现在有 $2$ 群奶牛 $i$ 和 $j$，可能 $S_i$ 被 $S_j$ 包含，也可能不互相包含。

如果 $S_i \subset S_j$，那么一定要先考虑 $S_i$ 能够取到的，否则可能 $j$ 取了 $S_i$ 集合中的而导致 $i$ 没有取满。

否则，就让 $i$ 贪心地优先取没有被 $S_j$ 包含的部分。

于是让所有奶牛集合按照 $(x_i - t_i, -x_i)$ 的二元组排序以保证被包含的集合先被考虑。用一个 set 维护苹果的集合，优先让奶牛匹配 $t_i + x_i$ 更小的苹果，暴力跳 set 即可。

至于复杂度，由于每次访问 set 中的元素都会使得要么删除一些苹果，要么删除一群奶牛，总的访问次数是 $O(n)$ 的，时间复杂度就是 $O(n \log n)$。

AC代码

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
 * @file:           T1.cpp
 * @author:         yaoxi-std
 * @url:            
*/
// #pragma GCC optimize ("O2")
// #pragma GCC optimize ("Ofast", "inline", "-ffast-math")
// #pragma GCC target ("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
using namespace std;
#define resetIO(x) \
    freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#define debug(fmt, ...) \
    fprintf(stderr, "[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)
template <class _Tp>
inline _Tp& read(_Tp& x) {
    bool sign = false; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) sign |= (ch == '-');
    for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
    return sign ? (x = -x) : x;
}
template <class _Tp>
inline void write(_Tp x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar((x % 10) ^ 48);
}
bool m_be;
using ll = long long;
using pii = pair<int, int>;
#define fi first
#define se second
const int MAXN = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n;
struct Node {
    int q, t, x, n;
    bool operator<(const Node& o) const {
        return x - t < o.x - o.t || (x - t == o.x - o.t && x > o.x);
    }
} a[MAXN];
bool m_ed;
signed main() {
    // debug("Mem %.5lfMB.", fabs(&m_ed - &m_be) / 1048576);
    read(n);
    for (int i = 1; i <= n; ++i)
        read(a[i].q), read(a[i].t), read(a[i].x), read(a[i].n);
    sort(a + 1, a + n + 1);
    multiset<pii> st; ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i].q == 1) {
            auto it = st.lower_bound({a[i].t + a[i].x, 0});
            while (a[i].n && it != st.end()) {
                int tmp = min(a[i].n, it->se);
                ans += tmp, a[i].n -= tmp;
                if (it->se == tmp) st.erase(it++);
                else st.insert({it->fi, it->se - tmp}), st.erase(it);
            }
        } else {
            if (a[i].n) st.insert({a[i].t + a[i].x, a[i].n});
        }
    }
    write(ans), putchar('\n');
    return 0;
}