贪心题。
如何找出正确的贪心策略呢？
我一开始是以为按照l排序，然后从1到n遍历，挑最大的满足的防晒霜。后来发现不行。挑最小的也不行。
看了题解发现是从n到1遍历。
为什么？
因为i-1的l比i的l承受能力要大些，我们只需考虑r！
而i+1的l比i的l承受能力要小一些！我们要两头考虑！失败！
然后是一些实现小细节了，包括手写二分......
#include <cstdio>
#include <algorithm>
/// poj 3614
using namespace std;
const int N = ;
int n, L;
struct Cow{
int a, b;
bool operator < (const Cow &x) const {
if(this->a != x.a) {
return this->a < x.a;
}
return this->b < x.b;
}
}c[N], a[N];
int main() {
scanf("%d%d", &n, &L);
for(int i = ; i <= n; i++) {
scanf("%d%d", &c[i].a, &c[i].b);
}
for(int i = ; i <= L; i++) {
scanf("%d%d", &a[i].a, &a[i].b);
}
sort(c + , c + n + );
sort(a + , a + L + );
int ans = ;
a[L + ].a = 0x7f7f7f7f;
/*
printf("\n");
for(int i = 1; i <= n; i++) {
printf("%d %d\n", c[i].a, c[i].b);
}
printf("\n");
for(int i = 1; i <= L + 1; i++) {
printf("%d %d\n", a[i], sum[i]);
}
printf("\n");
*/
for(int i = n; i >= ; i--) {
int p, l = , r = L + ;
while(l < r) {
p = (l + r) >> ;
if(a[p].a <= c[i].b) {
l = p + ;
}
else r = p;
}
if(a[p].a > c[i].b) p--;
//printf("%d ", p);
while(!a[p].b && a[p].a >= c[i].a) {
p--;
}
//printf("%d\n", p);
if(p && a[p].a <= c[i].b && a[p].a >= c[i].a) {
ans++;
a[p].b--;
}
}
printf("%d", ans);
return ;
}
AC代码