AcWing 110. 자외선 차단 제 (욕심)
12179 단어 여름방학 훈련 문제간단 한 문제욕심
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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU - 2006 기수 곱 하기홀수 의 곱셈 을 구하 다 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.