[VH1732] 업무 분담

문제

• ※ 문제 및 풀이에 대해 사외 온라인/오프라인에 게시/공유 하는 것은 금지되어 있습니다.  
     SW Expert 아카데미의 문제는 삼성전자 직원에게만 오픈 되어 있습니다.

  
  

   [제한 사항]
  
  

  시간	12개 테스트케이스를 합쳐서 C/C++의 경우 6초 / Java의 경우 12초 / Python의 경우 12초
  메모리	힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

  
  성삼 회사는 완벽한 업무분담을 꿈꾼다. 현재 회사에서 처리해야 할 일은 N개이다.

  
  각 업무 마다 한 명이 업무를 진행했을 때에 예상되는 소요 시간 t_i가 계산되어 있는 상태이다.

  
  또한 업무의 성격상 i번 업무는 i-1번 업무가 끝나기 전에는 시작할 수 없다.

  
  성삼 회사에는 유능한 K명의 사원이 있고 분업을 위해서 N개의 업무에 나눠서 투입된다.

  
  i번 업무에  p_i명이 투입 된다면 업무를 처리하는 시간이 t_i/p_i(= 업무 소요시간/ 투입된 사원수) 로 줄어들게 된다.

  
  모든 업무에는 적어도 최소 한 명은 투입되어야 한다.

  
  업무에 대한 정보와 사원수가 주어졌을 때, 모든 업무를 마치는 데에 필요한 최소 시간을 구하여라.

  
  

  
  

  [입력]

  
  첫 번째 줄에 테스트 케이스의 수 T가주어진다.

  
  

  각 테스트 케이스의 첫 번째 줄에는 업무 개수 N과 사원의 수 K(1 ≤ N ≤ K ≤ 10¹², N ≤ 10⁵) 가 주어지며 둘 다 자연수이다.

  
  두 번째 줄부터 각 줄 마다 t₁부터 t_n까지 차례대로 주어지며 모두 10¹²이하의 자연수이다.

  
  

  
  

  [출력]

  
  

  각 테스트 케이스마다 필요한 최소 시간을 소수점 첫째 자리에서 반올림하여 정수 형태로출력하라.

   
  

  입력 예제
  2 2 7 5 12 2 10 1 1024	// 테스트 케이스 개수 // 업무 개수 N , 사원의 수 K // 업무 1의 소요시간 // 업무 2의 소요시간

  
  
  

  출력 예제
  #1 5 #2 115	// 첫 번째 테스트 케이스 결과 // 두 번째 테스트 케이스 결과

  
   

  import java.util.Scanner; public class Solution {     static long t[] = new long [100000];     static double b;     static double c;     static double result;     static long k;     static long l;     static long r;     static long m;     static double sqrt(double a) {         b = 1;         c = 1;         for(int i = 0; i < 33; i++) {             c = (b + (a / b)) / 2;             if(b - c > 0 && b - c <= 0.001)                 return c;             else if(b - c < 0 && c - b <= 0.001)                 return c;             else                 b = c;                  }         return c;     }     public static void main(String argsp[]) throws Exception{         Scanner sc = new Scanner(System.in);         int T = sc.nextInt();         for(int test_case = 1; test_case <= T; test_case++) {             int N = sc.nextInt();             long K = sc.nextLong();             for(int i = 0; i < N; i++) {                 t[i] = sc.nextLong();             }             if(N == (int)K) {                 long result = 0;                 for(int i = 0; i < N; i++) {                     result += t[i];                 }                 System.out.println("#"+test_case+" "+result);                 continue;             }             double right = 1000000000000.;             double left = 0;             double mid = 0;             for(int j = 0; j < 75; j++) {                 mid = (right + left) / 2.;                 long sigma = 0;                 for(int i = 0; i < N; i++) {                     sigma += (long)((-1 + sqrt(1 + 4 * ((double)t[i] / (double)mid))) / 2.0) + 1;                 }                 if(sigma <= K)                     right = mid;                 else                     left = mid;             }             result = 0;             for(int i = 0; i < N - 1; i++) {                 k = 0;                 l = 1;                 r = K;                 while(l <= r) {                     m = (l + r) / 2;                     if((double)t[i] >= (double)right * (double)(m + 1) * (double)m) {                         l = m + 1;                         if(k < m)                             k = m;                     }else {                         r = m - 1;                     }                 }                 K -= (k + 1);                 result += (double)t[i] / (double)(k + 1);             }             result += (double)t[N-1] / (double) K;             System.out.println("#"+test_case+" "+(long)(result+0.5));         }         sc.close();     } }