USACO07NOV Sunscreen

未分类

Luogu

一道比较简单的贪心题

因为有两个限制条件，所以将所有奶牛按左端点降序排列，这样子一头奶牛能用的防晒霜也能满足后面所有牛的左端点限制。

这样子的话每次选防晒霜就选满足条件的最大的那个

正确性显然

#include <iostream>
#include <cstdio>
#include <algorithm>
const int MAXN = 2500 + 5;
int N, M, Ans;
int SPF[MAXN], Cover[MAXN];
struct Cow
{
    int l, r; 
} A[MAXN];
inline int read()
{
    register int x = 0;
    register char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
bool comp(Cow x, Cow y)
{
    return x.l > y.l;
}
int main()
{
    N = read();
    M = read();
    for(int i = 1; i <= N; ++i)
    {
        A[i].l = read();
        A[i].r = read();
    }
    for(int i = 1; i <= M; ++i)
    {
        SPF[i] = read();
        Cover[i] = read();
    }
    std::sort(A + 1, A + 1 + N, comp);
    for(int i = 1; i <= N; ++i)
    {
        int t = 0;
        for(int j = 1; j <= M; ++j)
            if(Cover[j] != 0 && SPF[j] >= A[i].l && SPF[j] <= A[i].r && SPF[j] > SPF[t]) t = j;
        if(t != 0) 
        {
            ++Ans;
            --Cover[t]; 
        } 
    }
    printf("%d\n", Ans);
    return 0;
}