글 읽기 - 놀이공원문제 질문입니다.. 어떤 예외가 있을까요?

aod0326 7년 전 0

80퍼대에서 틀렸다고 나오네요..

중간중간 막 수정하다보니 넘 복잡하게 짠거 같네요..ㅠ

대강의 논리는 일단 맨 처음에 놀이기구들이 비어있으니까 n<=m인 경우를 제외하고

n = n-m이라고 설정해서 시작했습니다.

binary search로 마지막 아이가 타기 전까지 걸린 시간을 찾고

각 놀이기구들마다 남은 시간을 따로 저장해서 시간순으로 먼저, 그리고 index순으로 정렬합니다.

그리고 마지막아이가 탈 index를 출력합니다...(이상 허접한 설명..ㅎ.)

앵간한것들은 다 맞게 나오는데 뭐가 틀렸는지 모르겠네요

import java.util.*;

public class Main {
	public static long[] max = {0,0};
	public static long count(int[] time, long t){
		long result = 0;
		for(int i=0;i<time.length;i++){
			result += t/time[i];
		}
		return result;
	}
	public static void findMin(int[] time, int n, long from, long to){
		if(from > to)
			return;
		long m = (from+to)/2;
		long c = count(time, m);
//		System.out.println("(m:"+m+", c:"+c+")");
		if(c >= (long)n){
			findMin(time, n, from, m-1);
		}else if(c < (long)n){
			if(m > max[0]){
				max[0] = m;
				max[1] = c;
			}
			findMin(time, n, m+1, to);
		}
	}
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();
    	int m = sc.nextInt();
    	int[] time = new int[m];
    	sc.nextLine();
    	StringTokenizer st = new StringTokenizer(sc.nextLine()," ");
    	int idx = 0;
    	while(st.hasMoreTokens()){
    		time[idx++] = Integer.parseInt(st.nextToken());
    	}
    	if(n <= m){
    		System.out.println(n);
    	}else{
    		long max_min = (long)((n-m)/m + 1)*30;//전부다 30분 일때
	    	findMin(time,n-m,1,max_min);
//	    	System.out.println(max[0]+" "+max[1]);
	    	int left = (n-m)-(int)max[1];
	    	int t = (int)max[0];
	    	Set[] s = new Set[m];
	    	for(int i=0;i<m;i++){
	    		s[i] = new Set(i,time[i]-(t%time[i]));
	    	}
	    	Arrays.sort(s,new SetComparator());
//	    	for(Set y : s){
//	    		System.out.println(y.time+" "+y.index);
//	    	}
	    	System.out.println(s[left-1].index+1);
    	}
    }
}
class Set{
	int index;
	int time;
	Set(int index, int time){
		this.index = index;
		this.time = time;
	}
}
class SetComparator implements Comparator<Set>{
	public int compare(Set A, Set B){
		int Ax = A.index; int Bx = B.index;
		int Ay = A.time; int By = B.time;
		if(Ay > By)
			return 1;
		else if(Ay < By)
			return -1;
		else{
			if(Ax > Bx)
				return 1;
			else
				return -1;
		}
	}
}

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

문제

문제

출처

ICPC

놀이공원문제 질문입니다.. 어떤 예외가 있을까요?

aod0326 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말