글 읽기 - 83% 틀렸습니다.

yepp0112 3년 전 0

이게 코드가 제가 생각한게 맞다면 틀린 것이 없는데 틀렸다고 나오네요...

제가 생각한 알고리즘

1.시작시간기준으로 정렬

2.다음 시작시간 - 지금 끝나는시간 >= m -> 지금 끝나는 시간에 시험 치룰 수 있음

3. 아닌 경우 지금 시험 치룰 수 없음

여기서 뭔 반례가 있나요??

코딩 고수님들 반례 부탁드립니다.ㅠㅠ

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

typedef struct{
	int start1;
	int end1;
}Class;

Class arr[100001];

int sortedx[100001];
int sortedy[100001];

void merge(int start,int mid,int end){
	int i=start;
	int j=mid+1;
	int index=start;
	
	while((i<=mid) && (j<=end)){
		if(arr[i].start1<arr[j].start1){
			sortedx[index]=arr[i].start1;
			sortedy[index]=arr[i].end1;
			
			i++;
		}
		
		else{
			sortedx[index]=arr[j].start1;
			sortedy[index]=arr[j].end1;
			
			j++;
		}
		
		index++;
	}
	
	if(i<=mid){
		for(int t=i;t<=mid;t++){
			sortedx[index]=arr[t].start1;
			sortedy[index]=arr[t].end1;
			
			index++;
		}
	}
	
	if(j<=end){
		for(int t=j;t<=end;t++){
			sortedx[index]=arr[t].start1;
			sortedy[index]=arr[t].end1;
			
			index++;
		}
	}
	
	for(int t=start;t<=end;t++){
		arr[t].start1=sortedx[t];
		arr[t].end1=sortedy[t];
	}
}

void mergeSort(int start,int end){
	if(start==end) return;
	
	int mid=(start+end)/2;
	mergeSort(start,mid);
	mergeSort(mid+1,end);
	
	merge(start,mid,end);
}

int main (){
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n,m,s;
	
	cin>>n>>m>>s;
	
	int i;
	
	for(i=0;i<n;i++){
		cin>>arr[i].start1>>arr[i].end1;
		arr[i].end1+=arr[i].start1;
	}
	
	mergeSort(0,n-1);
	
	/*for(i=0;i<n;i++){
		cout<<arr[i].start1<<' '<<arr[i].end1<<'\n';
	}*/
	int answer=-1;
	for(i=0;i<n;i++){
		if(i==n-1){
			if(s-arr[i].end1>=m) {
				answer=arr[i].end1;
				break;
			}
		}
		else{
			if(arr[i+1].start1-arr[i].end1>=m) {
				answer=arr[i].end1;
				break;	
			}
		}
	}
	
	if(answer != -1) cout<<answer;
	else cout<<answer;
	return 0;
}

yepp0112 3년 전 0

제가 앞쪽에 시간 비는 경우를 체크 안했었네요..

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

문제

문제

출처

ICPC

83% 틀렸습니다.

yepp0112 3년 전 0

yepp0112 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말