Advertisement
unknown_0711

Untitled

Aug 8th, 2022
730
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.18 KB | None | 0 0
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. public class Main {
  6.  
  7.     public static void main (String[] args) throws java.lang.Exception {
  8.         Scanner sc = new Scanner(System.in);
  9.         int n = sc.nextInt();
  10.         int [] arr = new int[n];
  11.         for (int i = 0; i < n; i++) {
  12.             arr[i] = sc.nextInt();
  13.         }
  14.         int B = sc.nextInt();
  15.       if(B>n){
  16.         System.out.print(-1);
  17.         return;
  18.       }
  19.         long sum = 0;
  20.         for (int i = 0; i < n; i++) {
  21.             sum = sum + arr[i];
  22.         }
  23.         long li = arr[0];
  24.         long hi = sum+100;
  25.         long res = -1;
  26.         while (li <= hi) {
  27.             long mid = (hi + li) / 2;
  28.             if (isAllocationPossible(arr, n, B, mid)) {
  29.                 res = mid;
  30.                 hi = mid - 1;
  31.             } else {
  32.                 li = mid + 1;
  33.             }
  34.         }
  35.         System.out.println(res);
  36.     }
  37.     public static boolean isAllocationPossible(int [] arr, int n, int B, long barrier) {
  38.         int student = 1;
  39.         long currentpages = 0;
  40.         for (int i = 0; i < n; i++) {
  41.             if (arr[i] > barrier) {
  42.                 return false;
  43.             }
  44.             if (currentpages + arr[i] > barrier) {
  45.                 student++;
  46.                 if (student > B) {
  47.                     return false;
  48.                 }
  49.                 currentpages = arr[i];
  50.             } else {
  51.                 currentpages = currentpages + arr[i];
  52.             }
  53.         }
  54.         return true;
  55.  
  56.     }
  57. }
  58.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement