Apple Catching (USACO Gold 2022 US Open)

Apple Catching (USACO Gold 2022 US Open)

简单推一下公式可以发现，tc+xc≥ta+xat_c+x_c \geq t_a+x_a而且tc−xc≥ta−xat_c-x_c \geq t_a-x_a的时候，牛(tc,ac)(t_c,a_c)可以接到苹果(ta,xa)(t_a,x_a)。所以我们可以替换坐标，变成(X=t+x,Y=t−x)(X=t+x,Y=t-x)（旋转45度），这样问题就变成平面上的二维点和线的关系问题。如下图所示：

每个奶牛（图中A、B、C、D），可以接住其右上方的苹果（蓝色点）。

有以下greedy算法可以完成任务：

  1. 将cow按Y从大到小排序，再按X从大到小，然后按这个顺序让cow取苹果，就是图中A、B、C、D的顺序。
  2. 维护一个动态的set，每次牛取苹果之前，按Y从大到小加入苹果到set中，直到当前cow的Y。同时，在set内部是按X从小到大排序。每一头牛从自己的XX开始在set中取苹果，直到用完自己可接的苹果数量，或者set里没有合适的苹果。

这个的正确性可以这样看：首先覆盖范围最小的cow（X,Y都是最大的，对应上图中区域“3”中的苹果）要优先取apple，这样才能保证这些牛的容量可以充分利用上；然后，当牛之间的范围没有绝对包含关系时，要从只有自己能覆盖的苹果开始取（例如对cow B来说，就是区域“1”），再取和别人有重合的（区域“2”）。这样可以保证当公有的苹果数量不足的时候，总的取得数量是最大的。做到这点的方法，就是在Y大于当前cow的Y的所有苹果中，按从左到右的顺序取苹果就可以了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n;
struct AC {
    int q,x,y;
    mutable int cnt;
    bool operator<(const AC &o) const {
        return x < o.x;
    }
};
vector<AC> pts;
bool cmpY(const AC &a, const AC &b) {
    if (a.y != b.y) return a.y > b.y;
    else return a.x > b.x;
}
multiset<AC> apples;
ll ans;
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int q, t, x, cnt;
        scanf("%d %d %d %d", &q, &t, &x, &cnt);
        pts.push_back({q, t+x, t-x, cnt});
    }
    sort(pts.begin(), pts.end(), cmpY);   // decreasing Y, then X
    for (AC &e: pts) {
        if (e.q == 1) { // cows
            while (e.cnt) {
                auto it = apples.lower_bound({2, e.x, 0, 0});
                if (it == apples.end()) break;
                if (it->cnt > e.cnt) {
                    it->cnt -= e.cnt;
                    ans += e.cnt;
                    e.cnt = 0;
                    break;
                }
                e.cnt -= it->cnt;
                ans += it->cnt;
                apples.erase(it);
            }
        } else {        // apple
            apples.insert(e);
        }
    }
    printf("%lld", ans);
 
    return 0;
}