[伯俊/Java]2343ギターレッスン



条件


  • 全部で講義する数はN個です.(1<= N <= 100,000 , int)

  • ブルーレイのM個数(1<=M<=N,int)

  • Blu-rayのサイズを最小にする必要があります->記録可能な分を指定した数で出力する必要があります
  • 入力例



    コード#コード#

    import java.io.*;
    import java.util.*;
    
    
    
    public class Main {
    	
    	static int N,M;
    	static int A[];
    	
    	
    	static FastReader scan = new FastReader();
    	static StringBuilder sb = new StringBuilder();
    
    	static void input() {
    	
    		N = scan.nextInt(); // 강의 개수를 받는다.
    		M = scan.nextInt(); // 블루레이의 개수를 받는다.
    		A = new int[N + 1]; // index를 1부터 시작하기 위해 + 1을 해준다.
    		for(int i=1;i<=N;i++) {
    			A[i] = scan.nextInt();
    		}
    	}
    
    	
    	static boolean findAns(int length) {
    	int cnt = 1 , sum =0;
    	for(int i = 1;i<=N ; i++) {
    		if(sum + A[i] > length) {
    			cnt++; // legth 길이보다 커지면 다음 블루레이를 사용하기 위해 ++을 해주고
    			sum = A[i]; // sum = A[i]를 넣어준다
    		}else {
    			sum +=A[i];
    		}
    	}
    	return cnt<=M; // 주어진 블루레이 개수 이하면 return을 해준다.
    	}
    	
    
    	static void find() {
    		int L =A[1], R = 100000000, ans =0; // L은 강의 첫 시간을 넣어주고 
            									// R은 int형 최대 수를 넣어준다.
    		for(int i= 1;i<=N;i++) L = Math.max(L, A[i]); // 제일 긴 녹화 길이는 해야하기 때문에 max로 최대값을 찾아준다.
    		
    		while(L<=R) {
    			int mid = (L + R ) / 2;
    			if(findAns(mid)) {
    				ans = mid;
    				R = mid -1;
    			}else {
    				L = mid +1 ;
    			}
    		}
    		System.out.println(ans);
    		}
    
    		
    		
    	public static void main(String[] args) {
    		input();
    		find();
    	}
    	
    	static class FastReader{
    		BufferedReader br;
    		StringTokenizer st;
    		
    		public FastReader() {
    			br = new BufferedReader(new InputStreamReader(System.in));
    		}
    		
    		public FastReader(String s) throws FileNotFoundException {
    			br = new BufferedReader(new FileReader(new File(s)));
    		}
    		
    		String next() {
    			while(st == null || !st.hasMoreElements()) {
    				try {
    					st = new StringTokenizer(br.readLine());
    				} catch(IOException e) {
    					e.printStackTrace();
    				}
    			}
    			return st.nextToken();
    		}
    		
    		int nextInt() {
    			return Integer.parseInt(next());
    		}
    		Long nextLong() {
    			return Long.parseLong(next());
    		}
    		double nextDouble(){
    			return Double.parseDouble(next());
    		}
    		String nextLine() {
    			String str = "";
    			try {
    				str = br.readLine();
    			}catch(IOException e) {
    				e.printStackTrace();
    			}
    			return str;
    		}
    	}
    }