본문 바로가기

카테고리 없음

[VH1732] 업무 분담

반응형

문제

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


     [제한 사항]

    시간

    12개 테스트케이스를 합쳐서 C/C++의 경우 6 / Java의 경우 12 / Python의 경우 12

        메모리

    , 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내


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


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


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


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


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


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


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



    [입력]


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


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


    두 번째 줄부터 각 줄 마다 t1부터 tn까지 차례대로 주어지며 모두 1012이하의 자연수이다.



    [출력]


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

     

    입력 예제

     

    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();
        }

     


반응형