【题解】P8272 [USACO22OPEN] Apple Catching G

EricQian · 2022-04-19 21:41:20 · 题解

P8272 [USACO22OPEN] Apple Catching G

题解

假设在 a(a_x,a_t) 点有奶牛，在 b(b_x,b_t) 有苹果 (a_t\le b_t)，a 可以借助 b 的充要条件为：

第二个式子直接 x-t 从小到大的顺序搞定（注意如果值相同 t 大的优先），这样只要每个数匹配在它之前的点就都是合法的，接下来只用满足第一个式子。

考虑两头奶牛 a_1,a_2(a_x-a_t<b_x-b_t) 一起匹配苹果，我们会让 a_1 优先匹配苹果中 b_x+b_t 最小的，把剩下的留给 a_2。

为什么这样是对的呢？

显然 b_x+b_t 越小越难被匹配，那么如果可以被匹配，直接匹配一定最优。

而且如果 a_1 与 a_2 都能够匹配同一个 b，让他们任何一个去匹配是相同的。

那么就这样被简单地证明了。

实际操作中可以用 multiset 来支持查询比 a_x+a_t 大的数即可。

代码

// Author:A weak man named EricQian
#include<bits/stdc++.h>
using namespace std;
#define infll 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define Maxn 200005
#define pb push_back
#define pa pair<int,int>
#define fi first
#define se second
typedef long long ll;
inline int rd()
{
    int x=0;
    char ch,t=0;
    while(!isdigit(ch = getchar())) t|=ch=='-';
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x=t?-x:x;
}
inline ll maxll(ll x,ll y){ return x>y?x:y; }
inline ll minll(ll x,ll y){ return x<y?x:y; }
inline ll absll(ll x){ return x>0ll?x:-x; }
inline ll gcd(ll x,ll y){ return (y==0)?x:gcd(y,x%y); }
int m,ans;
struct OPT
{
    int opt,t,x,num;
    bool friend operator < (OPT a,OPT b)
        { return (a.x-a.t!=b.x-b.t)?(a.x-a.t<b.x-b.t):(a.x>b.x); }
}c[Maxn];
multiset<pa> Left;
int main()
{
    //ios::sync_with_stdio(false); cin.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    m=rd();
    for(int i=1;i<=m;i++) c[i]=(OPT){rd(),rd(),rd(),rd()};
    sort(c+1,c+m+1);
    for(int i=1;i<=m;i++)
    {
        if(c[i].opt==1)
        {
            auto it=Left.lower_bound(pa(c[i].x+c[i].t,0));
            while(c[i].num && it!=Left.end())
            {
                int tmp=min(it->se,c[i].num);
                c[i].num-=tmp,ans+=tmp;
                if(tmp==(it->se)) Left.erase(it++);
                else Left.insert(pa(it->fi,(it->se)-tmp)),Left.erase(it);
            }
        }
        else Left.insert(pa(c[i].x+c[i].t,c[i].num));
    }
    printf("%d\n",ans);
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}