题解 P2887 【[USACO07NOV]防晒霜Sunscreen】
小黑AWM
2019-01-30 15:46:25
没有看到过用set的，贪心策略证明就不讲了，其他题解中有一位神仙详细的证明了，主要就是分类讨论当前是否采取贪心对后续过程的影响。
我的策略是：
**首先将线段按照左端点从大到小排序，然后从大到小地选择可用的防晒霜给奶牛上霜。就是尽量选择右边的点。**
那么我采用的是一个set来维护这个事情，每次在set中查找最后一个不大于他的数，总复杂度还是严格的O(nlogl)
~~不要问我为什么不用Priority_queue我只是想玩一下~~
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int maxn = 2505;
int c, l, SPF, cover[10000], ans;
pair<int, int> cow[maxn];
set<int> spf;
bool cmp(pair<int,int> a, pair<int,int> b){
return a.first > b.first;
}
int main(){
cin >> c >> l;
for(int i = 1; i <= c; i++)
cin >> cow[i].first >> cow[i].second;
sort(cow+1, cow+1+c, cmp);
int temp;
for(int i = 1; i <= l; i++){
cin >> SPF >> temp;
spf.insert(SPF);
cover[SPF] += temp;
}
for(int i = 1; i <= c; i++){
set<int>::iterator p = spf.lower_bound(cow[i].second);
if(p == spf.end())
p--;
while(*p > cow[i].second){
if(p == spf.begin())
goto nxt;
p--;
}
if(*p < cow[i].first)
continue;
ans++;
cover[*p]--;
if(cover[*p] == 0)
spf.erase(p);
nxt : cerr << cow[i].second << "-" << *p << endl;
}
cout << ans << endl;
return 0;
}
```