中南高校2012年6月月赛 Problem F: 羊吃草 贪心

      Like so many others, the sheep have developed very haughty tastes and will no longer graze on just any grass. Instead, Mr.Lee , the owner of the fram must purchase gourmet organic grass at the Green Grass Grocers store for each of his N (1 <= N <= 100,000) sheep.

     Each sheep_i demands grass of price at least A_i (1 <= A_i <=1,000,000,000) and with a greenness score at least B_i (1 <= B_i<= 1,000,000,000). The GGG store has M (1 <= M <= 100,000) different types of grass available, each with a price C_i (1 <= C_i <=1,000,000,000) and a greenness score of D_i (1 <= D_i <= 1,000,000,000).Of course, no sheep would sacrifice her individuality, so no two sheep can have the same kind of grass.

     The input contains several test cases. each test case contains two space-separated  integers: N and M. The next N lines contains two space-separated integers: A_i and B_i. Then next M lines contains two space-separated integers: C_i and D_i

 A single integer which is the minimum cost to satisfy all the sheep. If that is not possible, output -1.

/*
这是一个贪心的题目，贪心的策略是这样的，将供应按照greenness从大到小排序，将
需求也按照greenness从大到小排序，然后按照greenness 从大到小依次枚举每个需求，
对于每个满足greenness条件的供应，我们选择price最小的那个作为当前需求的供应。
这种贪心策略可以这样证明：因为供应和需求都是按照greenness从大到小排序的，对于
当前的这个需求可以选择的供应一定是那些greenness都比它大的，假设现在有两个选择
choice1 , choice2 他们的greenness都满足当前的需求，但是choice1.price < choice2.price
如果这个时候我们选择choice2的话，choice1有两种可能，一种可能是最后没有一个需
求选它， 那么这个时候我们将choice2换成choice1显然会得到更优解； 还有一种可能
性是choice1在后面的需求中被选中，这时候我们交换choice1和choice2的选择之后，不
但没有产生冲突（仍然满足题意的条件），而且总的price也没有增加。因此我们可以总
结上面的分析得出一个结论就是：选择greenness满足条件的最小price并不会使得解更差，
因此我们这样的贪心策略是正确的。
*/
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#include<set>
typedef long long LL ;
int N , M ;
std::vector< std::pair<int, int> >  v1,v2 ;
std::set< std::pair<int, int> >  ss ;

int main(){
    int a,b,r;
    while(scanf("%d %d",&N,&M) == 2)
    {
        v1.clear(); v2.clear() ;
        for(int i=1;i<=N;i++)
        {
            scanf("%d %d",&a,&b);
            v1.push_back( std::make_pair(b,a) );
        }
        for(int i=1;i<=M;i++)
        {
            scanf("%d %d",&a,&b);
            v2.push_back( std::make_pair(b,a) ) ;
        }
        std::sort( v1.begin() , v1.end() );
        std::sort( v2.begin() , v2.end() );

        ss.clear() ;
        r = M - 1 ;
        LL ans = 0 ;
        bool ok = 1 ;
        for(int i=N-1;i>=0;i--)
        {
            while( 1 )
            {
                if(r < 0)  break ;
                if( v2[r].first >= v1[i].first )    ss.insert( std::make_pair( v2[r].second ,r) ) ;
                else        break ;
                r -- ;
            }
            std::set< std::pair<int, int> >::iterator d = ss.lower_bound( std::make_pair( v1[i].second , -1) );
            if( d == ss.end() )
            {
                printf("-1\n") ;    ok = 0 ;
                break ;
            }
            ans += (*d).first ;
            ss.erase( d ) ;
        }
        if( ok )    printf("%lld\n",ans) ;
    }
    return 0 ;
}