AcWing 110. 자외선 차단 제 (욕심)

문제:
C 마리 의 젖소 가 일광욕 을 하고, i 마리 의 젖 소 는 minSPF [i] 에서 maxspf [i] 단위 강도 사이 의 햇빛 이 필요 하 다.
젖소 한 마 리 는 일광욕 전에 반드시 자외선 차단 제 를 발 라 야 한다. 자외선 차단 제 는 L 종이 고, i 종 을 바 르 면 몸 에서 받 는 햇빛 의 강 도 는 SPF [i] 로 안정 되 며, i 종 자외선 차단 제 는 cover [i] 병 이 있다.
최대 몇 마리 의 젖소 가 일광욕 을 할 수 있 는 지 를 구하 다.
1≤C,L≤2500 1≤minSPF≤maxSPF≤1000 1≤SPF≤1000
생각:
우 리 는 소 를 받 아들 이 는 하한 선 에 따라 큰 것 에서 작은 것 으로 정렬 하고 하한 선 이 같 을 때 상한 선 에 따라 큰 것 에서 작은 것 으로 정렬 합 니 다.그리고 자외선 차단 제 를 큰 것 부터 작은 것 까지 정렬 하고 같은 시간 에 수량 에 따라 큰 것 부터 작은 것 까지 정렬 합 니 다.이렇게 하면 모든 소 에 게 찾 을 수 있 는 것 은 그 조건 을 만족 시 키 는 가장 큰 자외선 차단 제 이다. 그리고 현재 소의 선택 이 뒤의 소 에 게 영향 을 미 치 는 지 고려 해 야 한다.소 A, B 에 게 는 자외선 차단 제 X, Y 가 있다.X, Y 가 모두 A 의 조건 을 충족 하면 반대편 B 에 게 ① X, Y 모두 만족 (B 의 상한 > A 의 상한) ② X, Y 모두 만족 하지 않 음 (B 의 상한 선 ③ X 가 만족 하지 않 으 면 Y 만족 (B 의 상한 선 은 Y 위, X 아래) 은 X 만족 이 존재 하지 않 고 Y 가 만족 하지 않 기 때문에 A 의 선택 은 B 에 영향 을 주지 않 는 다. 이 는 국부 적 으로 가장 좋 은 것 을 내 놓 을 수 있다 는 것 을 의미한다.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
using namespace std;
struct stu
{
    int down;
    int up;
}cow[3000];
struct ru
{
    int co;
    int spf;
}r[3000];
bool cmp(stu a,stu b)
{
    if(a.down==b.down)
        return a.up>b.up;
    else
        return a.down>b.down;
}
bool cmp1(ru a,ru b)
{
    if(a.spf!=b.spf)
        return a.spf>b.spf;
    else
        return a.co>b.co;
}
int main()
{
    int c,l,ans=0;
    scanf("%d%d",&c,&l);
    for(int i=0;i<c;i++){
        scanf("%d%d",&cow[i].down,&cow[i].up);
    }
    for(int i=0;i<l;i++){
        scanf("%d%d",&r[i].spf,&r[i].co);
    }
    sort(cow,cow+c,cmp);
    sort(r,r+l,cmp1);
    for(int i=0;i<c;i++){
        int flag=0;
        for(int j=0;j<l;j++){
            if(r[j].spf<=cow[i].up&&r[j].co>0&&r[j].spf>=cow[i].down){
                flag=1;
                r[j].co--;
                break;
            }
        }
        if(flag)
            ans++;
    }
    printf("%d
"
,ans); return 0; }

좋은 웹페이지 즐겨찾기