Facebook
From Trivial Bird, 1 Year ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 112
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4. public class Main
  5. {
  6.         public static long minimumPossibleNumber(long arr[],int n,long m){
  7.                 long min=Integer.MIN_VALUE;
  8.                 long max=0L;
  9.                 for(int i=0;i<n;i++){
  10.                         if(arr[i]>min){
  11.                                 min=arr[i];
  12.                         }
  13.                         max+=arr[i];
  14.                 }
  15.                 Long low=0L;
  16.                 long high=max;
  17.                 long res=-1L;
  18.                 while(low<=high){
  19.                         long mid=low+(high-low)/2;
  20.                         if(isPossible(arr ,n,m,mid)){
  21.                                 res=mid;
  22.                                 high=mid-1L;
  23.                         }
  24.                         else{
  25.                                 low=mid+1L;
  26.                         }
  27.                 }
  28.                 return res;
  29.         }
  30.         public static boolean isPossible(long arr[] ,int n ,long  m,long mid ){
  31.                 long studentCount=1L;
  32.                 long pageCount=0L;
  33.                 for(int i=0;i<n;i++){
  34.                         if(pageCount+arr[i]<=mid){
  35.                                 pageCount+=arr[i];
  36.                         }
  37.                         else{
  38.                                 studentCount++;
  39.                                 if(studentCount>m||arr[i]>mid){
  40.                                         return false;
  41.                                 }
  42.                                 pageCount=arr[i];
  43.                         }
  44.                 }
  45.                 return true;
  46.         }
  47.         public static void main (String[] args) throws java.lang.Exception
  48.         {
  49.                 //your code here
  50.                 Scanner sc=new Scanner(System.in);
  51.                 int n=sc.nextInt();
  52.                 long arr[]=new long [n];
  53.                 for(int i=0;i<n;i++){
  54.                         arr[i]=sc .nextLong();
  55.                 }
  56.                 long m=sc.nextLong();
  57.                 long ans=minimumPossibleNumber(arr,n,m);
  58.                 System.out.print(ans);
  59.         }
  60. }