baike 2020-04-15
证明不会:yxc说要用匈牙利算法,来确定增广路径;
算法步骤:
1.将牛按minspf从大到小排序
2.每次取出满足当前条件,最大的spf。
因为是按开始从大到小排序,所以假设x, y防晒,spfs[x] < spfs[y], 那么可能后面的牛能用到x,y,或者只用到x,或者都用不上。因为后面的牛可能可以用x,所以当前这头牛应该选择在它适合的范围最大的spf。
所以结论成立。
代码
#include <iostream> #include <algorithm> #include <map> using namespace std; typedef pair<int, int> PII; const int N = 2500 + 5; PII cows[N]; int main(){ int c,l; cin >> c >> l; map<int, int> spfs; for(int i = 0; i < c; ++ i)cin >> cows[i].first >> cows[i].second; for(int i = 0; i < l; ++ i){ int spf, cover; cin >> spf >> cover; spfs[spf] += cover; } sort(cows, cows+c); int res = 0; spfs[0] = spfs[1001] = c; //auto spf = spfs.upper_bound(cows[i].second); //这句话是在spfs中查找大于cows[i].second的最小元素 //,设置哨兵是为了让这条语句不返回空。 for(int i = c-1; i >= 0; -- i){ auto spf = spfs.upper_bound(cows[i].second);//找出第一个大于它的数 spf--; if(spf->first >= cows[i].first){ res++; if(--spf->second == 0) spfs.erase(spf); } } cout << res << endl; return 0; }