7243 : 정렬 종합 2
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 작업이 있으며, 각 작업은 소요 시간과 마감 기한을 가집니다.
마감 기한을 넘기지 않고 완료할 수 있는 작업의 수를 최대화하는 최적 순서를 구하십시오.
이 문제는 그리디 알고리즘으로 최적해를 보장합니다: 마감 기한 오름차순으로 정렬하여 가능한 작업을 순서대로 선택합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
마감 기한을 넘기지 않고 완료할 수 있는 작업의 수를 최대화하는 최적 순서를 구하십시오.
이 문제는 그리디 알고리즘으로 최적해를 보장합니다: 마감 기한 오름차순으로 정렬하여 가능한 작업을 순서대로 선택합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 작업 수 $N$이 주어집니다. ($1 \le N \le 100{,}000$)
이어서 $N$개의 줄에 각 작업의 소요 시간 $t$와 마감 기한 $d$가 주어집니다. ($1 \le t, d \le 10^9$)
이어서 $N$개의 줄에 각 작업의 소요 시간 $t$와 마감 기한 $d$가 주어집니다. ($1 \le t, d \le 10^9$)
출력 설명
첫째 줄에 최대로 처리할 수 있는 작업의 수를 출력합니다.
둘째 줄에 선택된 작업의 원래 번호(1-based)를 오름차순으로 공백 구분하여 출력합니다.
단, 선택된 작업이 없으면 둘째 줄을 출력하지 않습니다.
둘째 줄에 선택된 작업의 원래 번호(1-based)를 오름차순으로 공백 구분하여 출력합니다.
단, 선택된 작업이 없으면 둘째 줄을 출력하지 않습니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
1 2
2 4
3 6
1 8
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4
1 2 3 4도움
마감 기한 오름차순으로 정렬한 후, 현재 누적 시간과 마감 기한을 비교합니다.
누적시간 + 소요시간 <= 마감기한이면 해당 작업을 선택합니다.