탐욕 알고리즘 Problem B 1001
제목: 기계 로 몇 개의 나 무 를 처리 하고 첫 번 째 나 무 를 처리 하 는 데 1 분 의 적재 시간 이 필요 합 니 다. 다음 나무의 길이 와 너비 가 이전 보다 크 면 이 나 무 는 적재 시간 이 필요 하지 않 습 니 다. 그렇지 않 으 면 똑 같이 1 분 이 걸 립 니 다.몇 개의 그룹 데 이 터 를 제시 하여 각각 가장 짧 은 적재 시간 을 구하 세 요.
문제 풀이 사고의 형성 과정: 먼저 정렬 을 하고 길 거나 넓 은 것 중 하나 에 따라 정렬 하면 된다.그 다음 에 순환 에서 그룹 을 나 누고 한 그룹 이 실 행 된 후에 erase 를 없 애고 다음 그룹의 계산 을 합 니 다.
소감: 앞의 문제 와 대체적으로 같 지만 다른 점 을 가 려 야 한다.크 거나 크 거나 같 습 니 다. 이 때 맵 을 사용 하 시 겠 습 니까? 멀 티 맵 을 사용 하 시 겠 습 니까?그 밖 에 multimap 의 할당 은 insert (Make pair () 로 만 이 루어 질 수 있 고 mulitimap [first] = second;의 방법 은 무효 이 므 로 사용 할 수 없습니다.
코드:
#include<iostream>
#include<map>
using namespace std;
int main()
{
int m;
cin>>m;
while(m--){
int n,t=0;
multimap <int,int> s;// ， map 。
multimap <int,int>::iterator si,sii,siii;
cin>>n;
while(n--){
int p,q;
cin>>p>>q;
s.insert(make_pair(p,q));// s[p]=q;
}
for(si=s.begin();si!=s.end();){
siii=si;
siii++;
int ll=si->first;
int ww=si->second;
if(siii==s.end()) {t+=1; break;}
for(sii=si;sii!=s.end();){
if(sii==si) ++sii;
if(sii->first>=ll&&sii->second>=ww)// ， > >=
{ll=sii->first;
ww=sii->second;
s.erase(sii++);}
else
++sii;
}
s.erase(si++);
t+=1;
}
s.clear();
cout<<t<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
