글 읽기 - 45%에서 막히네요 반례 알려주시면 감사하겠습니다

hnduddn 2년 전 0

반례 알려주시면 감사하겠습니다

#include <iostream>
#include <algorithm>
using namespace std;

void sort(int arr[][2], int size) {
	int max, index;
	for (int i = 0; i < size - 1; i++) {
		max = arr[i][0];
		index = i;
		for (int j = i + 1; j < size; j++) {
			if (max < arr[j][0]) {
				max = arr[j][0];
				index = j;
			}
			else if (max == arr[j][0]) {
				if (arr[index][1] < arr[j][1])
					index = j;
			}
		}
		int temp = arr[i][0];
		arr[i][0] = arr[index][0];
		arr[index][0] = temp;

		temp = arr[i][1];
		arr[i][1] = arr[index][1];
		arr[index][1] = temp;
	}
}

int main() {
	int n, during, min, endtime;
	int arr[1001][2];

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> during >> endtime;
		arr[i][0] = endtime - during; arr[i][1] = endtime;
	}

	sort(arr, n);//끝내야할 시간에서 걸리는 시간을 뺀 (가장 늦게 시작할수 있는 시간 기준으로 정렬)
                 //시간이 같을경우 끝내야할 시간을 기준으로 더 늦게 끝내야할 시간이 앞으로 오게함

	min = arr[0][0];
	for (int i = 1; i < n; i++) {
		if (min < arr[i][1]) {   //시간이 겹칠경우
			min -= arr[i][1] - arr[i][0];
		}
		else    //시간이 안겹칠경우
			min = arr[i][0];
	}

	if (min < 0)
		cout << -1;
	else {
		cout << min;
	}
}

hnduddn 2년 전 0

아 정렬하는 방법을 바꿧더니 해결됐네요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

45%에서 막히네요 반례 알려주시면 감사하겠습니다

hnduddn 2년 전 0

hnduddn 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말