中南高校2012年6月月赛 Problem F: 羊吃草 贪心
中南大学2012年6月月赛 Problem F: 羊吃草 贪心Problem F: 羊吃草/*这是一个贪心的题目，贪心的策略是这样
中南大学2012年6月月赛 Problem F: 羊吃草 贪心
Problem F: 羊吃草/*这是一个贪心的题目，贪心的策略是这样的，将供应按照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 ;}
