BZOJ 1691 [Usaco2007 Dec]挑剔的美食家 multiset_排序_贪心

Code:

#include<bits/stdc++.h>
#define setIO(s) freopen(s".in","r",stdin) 
#define maxn 100000 
using namespace std;           
multiset<int>S; 
struct Cow{ 
    int a,b;  
    Cow(int a=0,int b=0):a(a),b(b){} 
    bool operator<(Cow c)const{ return b==c.b ? a > c.a : b > c.b;   }
}cow[maxn];
struct Grass{
    int a,b; 
    Grass(int a=0,int b=0):a(a),b(b){} 
    bool operator<(Grass c)const{ return c.b==b ? a < c.a : b > c.b;  }
}G[maxn]; 
int main(){
    // setIO("input"); 
    int n,m,j=0; 
    long long ans=0; 
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d%d",&cow[i].a,&cow[i].b); 
    for(int i=1;i<=m;++i) scanf("%d%d",&G[i].a,&G[i].b);         
    sort(cow+1,cow+1+n),sort(G+1,G+1+m); 
    for(int i=1;i<=n;++i){ 
        while(j<m&&G[j+1].b>=cow[i].b) S.insert(G[++j].a); 
        multiset<int>::iterator it=S.lower_bound(cow[i].a);
        if(it==S.end())
        {
            printf("-1\n"); 
            return 0;
        }
        ans+=(long long)*it; 
        S.erase(it);
    }
    printf("%lld\n",ans); 
    return 0; 
}

  

上一篇:牛的舞会The Cow Prom


下一篇:BZOJ 1666: [Usaco2006 Oct]Another Cow Number Game 奶牛的数字游戏 幼儿园测试题