【POJ3614】Sunscreen

            

problem

有C个奶牛去晒太阳,第i头奶牛需要minSPF[i]和maxSPF[i]单位强度之间的阳光。每头奶牛晒太阳之前要涂防晒霜,防晒霜有L种,涂上第i种以后阳光强度就会稳定为SPF[i],第i种防晒霜有cover[i]瓶。求最多可以满足多少头奶牛晒太阳。(1 <=C,L<= 2500)

solution

按照minSPF递减的顺序把奶牛排序,依次考虑每头奶牛。
对于每头奶牛,扫描所有能用的防晒霜,找一个最大的用了。

贪心,可用范围缩放证明。
考虑当前奶牛用了防晒霜后的范围拓展到后来的奶牛。
对于两头奶牛x,y,一瓶防晒霜会出现1.x,y都可以用,2.x可以用,y不能用,3.x,y都不能用三种情况,因为已经按照minSPF[i]降序排序了,所以越小的防晒霜,后面的奶牛才有越大的可能会用到。

好激动,第一次自己写没看题解而且一遍就过了。。。

codes

#include
#include
using namespace std;
const int maxn = 2520;
int C, minSPF[maxn], maxSPF[maxn], r1[maxn];
int L, SPF[maxn], cover[maxn], r2[maxn];
bool cmp1(int a, int b){return minSPF[a]>minSPF[b];}
bool cmp2(int a, int b){return SPF[a]>SPF[b];}
int main(){
    //input
    cin>>C>>L;
    for(int i = 1; i <= C; i++)
        cin>>minSPF[i]>>maxSPF[i];
    for(int i = 1; i <= L; i++)
        cin>>SPF[i]>>cover[i];
    //sort
    for(int i = 1; i <= C; i++)r1[i] = i;
    sort(r1+1,r1+C+1,cmp1);
    for(int i = 1; i <= L; i++)r2[i] = i;
    sort(r2+1,r2+L+1,cmp2);
    //do
    int ans = 0;
    for(int i = 1; i <= C; i++){
        for(int j = 1; j <= L; j++){
            if(cover[r2[j]] && minSPF[r1[i]]<=SPF[r2[j]] && SPF[r2[j]]<=maxSPF[r1[i]]){
                ans++;  cover[r2[j]]--;
                break;
            }
        }
    }
    cout<'\n';
    return 0;
}
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像