[Usaco2007 Dec]挑剔的美食家

题目描述

与很多奶牛一样,Farmer John那群养尊处优的奶牛们对食物越来越挑剔,随便拿堆草就能打发她们午饭的日子自然是一去不返了。现在,Farmer John不得不去牧草专供商那里购买大量美味多汁的牧草,来满足他那N(1 <= N <= 100,000)头挑剔的奶牛。 所有奶牛都对FJ提出了她对牧草的要求:第i头奶牛要求她的食物每份的价钱不低于A_i(1 <= A_i <= 1,000,000,000),并且鲜嫩程度不能低于B_i(1 <= B_i <= 1,000,000,000)。商店里供应M(1 <= M <= 100,000)种不同的牧草,第i 种牧草的定价为C_i(1 <= C_i <= 1,000,000,000),鲜嫩程度为D_i (1 <= D_i <= 1,000,000,000)。 为了显示她们的与众不同,每头奶牛都要求她的食物是独一无二的,也就是说,没有哪两头奶牛会选择同一种食物。 Farmer John想知道,为了让所有奶牛满意,他最少得在购买食物上花多少钱。

输入格式

第1行: 2个用空格隔开的整数:N 和 M
第2..N+1行: 第i+1行包含2个用空格隔开的整数:A_i、B_i * 第N+2..N+M+1行: 第j+N+1行包含2个用空格隔开的整数:C_i、D_i

输出格式

第1行: 输出1个整数,表示使所有奶牛满意的最小花费。如果无论如何都无法 满足所有奶牛的需求,输出-1

分析:

二维偏序,直接上其他东西也可以,然后我想练练cdq分治…
然后我们第一维排序,第二维分治…

代码:

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define db double
#define fi first
#define se second
const LL N=1e5+10;
const LL inf=0x3f3f3f3f;
const LL mod=12345678;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
namespace Treap
{
    int cnt=0,root;
    struct Node {LL key;int siz,p,ch[2];}node[N];
    Node new_node(LL key)
    {
        node[++cnt].key=key;
        node[cnt].p=rand();
        node[cnt].siz=1;
    }
    void updata(int now)
    {
        int l=node[now].ch[0],r=node[now].ch[1];
        node[now].siz=node[l].siz+node[r].siz+1;
    }
    int merge(int x,int y)
    {
        if(node[x].siz==0) return y;
        if(node[y].siz==0) return x;
        if(node[x].p<node[y].p)
        {
            node[x].ch[1]=merge(node[x].ch[1],y);
            updata(x);return x;
        }
        else
        {
            node[y].ch[0]=merge(x,node[y].ch[0]);
            updata(y);return y;
        }
    }
    void split_k(int now,int &x,int &y,int k)
    {
        if(node[now].siz==0) {x=y=0;return;}
        if(node[node[now].ch[0]].siz+1<=k) x=now,split_k(node[now].ch[1],node[now].ch[1],y,k-node[node[now].ch[0]].siz-1);
        else y=now,split_k(node[now].ch[0],x,node[now].ch[0],k);
        updata(now);
    }
    void split_key(int now,int &x,int &y,LL k)
    {
        if(node[now].siz==0) {x=y=0;return;}
        if(node[now].key<=k) x=now,split_key(node[now].ch[1],node[now].ch[1],y,k);
        else y=now,split_key(node[now].ch[0],x,node[now].ch[0],k);
        updata(now);
    }
    int a,b,c,d,e,f;
}
using namespace Treap;
LL ans;
int n,m;
struct No{LL a,b;}niu[N],cao[N];
bool cmp(No x,No y){return x.b>y.b;}
signed main()
{
    read(n),read(m);
    for(int i=1;i<=n;i++) read(niu[i].a),read(niu[i].b);
    for(int i=1;i<=m;i++) read(cao[i].a),read(cao[i].b);
    sort(niu+1,niu+n+1,cmp);
    sort(cao+1,cao+m+1,cmp);
    int now=1;
    for(int i=1;i<=n;i++)
    {
        while(cao[now].b>=niu[i].b) 
        {
            new_node(cao[now].a);
            split_key(root,a,b,cao[now].a);
            a=merge(a,cnt);
            root=merge(a,b);
            now++;
        }
        split_key(root,a,b,niu[i].a-1);
        split_k(b,c,d,1);
        if(node[c].key<niu[i].a) return 0*puts("-1");
        ans+=node[c].key;
        root=merge(a,d);
    }
    printf("%lld\n",ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注