P8272 [USACO22OPEN] Apple Catching G

洛谷

先考虑推导式子。

设我们选择的奶牛为 \(i\),选择的苹果是 \(j\)。

那么可以得到式子：

\[|x_i-x_j|\le t_j-t_i \]

直接拆掉绝对值，因为绝对值会取较大的值，所以不需要考虑二者大小关系的影响，然后即可推得两式：

\[x_i+t_i\le t_j+x_j \]

\[t_i-x_i\le t_j-x_j \]

仅在满足以上条件时可以拿到苹果。

那么此时我们就有了一个统一的衡量标准，经典的贪心思路是，对于每一个奶牛，我们去选择可以拿到，且最不容易被其它奶牛拿到的苹果。

因为苹果和奶牛在本质上没有区别，所以也可以让苹果去找奶牛。

我们将其中的一个量设置为一维，通过排序解决，另外一个量设为第二维，可以二分答案，为了方便插入删除以及二分查找，比较容易想到用一个 set 维护第二维。

那么我们就贪心的去选择接的苹果即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,ans;
struct P{int op,x,y,n;
}a[200005];
bool cmp(P a,P b){if(a.x!=b.x)return a.x>b.x;return a.y>b.y;
}
set<pair<int,int>> s;
signed main(){cin>>n;for(int i=1,t,x;i<=n;i++){cin>>a[i].op>>t>>x>>a[i].n;a[i].x=t+x,a[i].y=t-x;}sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){if(a[i].op==2)s.insert({a[i].y,i});else {while(a[i].n){auto it=s.lower_bound({a[i].y,0});if(s.end()==it)break;pair<int,int> tmp=*it;int id=tmp.second;int res=min(a[id].n,a[i].n);a[id].n-=res;a[i].n-=res;ans+=res;if(!a[id].n)s.erase(it);}}}cout<<ans;return 0;
}