📙[Algo] 24.01.03 알고리즘

31059번: Haybale Distribution

문제요약
정수 지점(xi)에 위치한 N개의 헛간
각각의 헛간으로 하나씩 건초더미 배달
   - 현재 건초더미는 y지점에 존재한다.
배달 과정에서 거리 당 일정량이 낭비됨
   - y → x
     * 만약 y ≥ x, ai 단위의 건초가 낭비
     * 만약 y<x, bi 단위의 건초가 낭비

시간제한
2

입력
헛간 개수 N (1 ≤ N ≤ 2*10만)
헛간의 좌표 x1… xN (0 ≤ xi ≤ 100만)
Q개의 질문 (1 ≤ Q ≤ 2*10만)
Q개 정수쌍 (ai, bi)

출력
각 질문별로 최소 낭비량 계산

 

접근법

• 누적합과 이분탐색을 사용해서 푸는 문제라고 한다.
• 주어진 헛간 위치가 1 2 3 4 10 이니까
  • 위치 가능한 건초 위치는 1~10사이라고 생각
• 만약 y를 5라고 생각할 때
  • 왼쪽 : (5 - 1)*a + (5 - 2)*a + (5 - 3)*a + (5 - 4)*a
  • 오른쪽 : (10 - 5)*b
  ⇒ 즉 a*(왼쪽에 위치한 헛간 개수 * 5 -1 - 2 - 3 - 4) + b*(10 - 오른쪽에 위치한 헛간 개수*5)
• 주어질 수 있는 쿼리개수도 많으므로 이미 한 번 방문한 y지점에서 낭비량의 경우 기록해야함 ⇒ 즉, y기준 왼쪽에 위치한 헛간 개수를 기록하자
• 누적합 입력

• 이분탐색으로 최소 낭비가 되는 y값 찾기
• 만약 쿼리가 a=1, b=4라면
• start = 1, end = 10, y=5
  • if(barns[idx]-5 ≤ 0)
    • 1 * (y보다 작은 위치 개수*5 - (arr[3]))
  • else if(barns[idx]-5 > 0)
    • 4 * ((arr[4]-arr[3]) - y보다 큰 위치 개수*5)

 

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N; // 헛간 개수
    static int[] barns; // 헛간 위치 담은 배열
    static long[] prefix;
    static long[] suffix;
    static int Q; // 쿼리 개수
    static int a=0, b=0; // a,b 가중치 변수

    static long calCost(int y){
        // 이게 무슨뜻이지..?
        if (y < 0 || y > 1000000) {
            return Long.MAX_VALUE;
        }
        return a*prefix[y] + b*suffix[y];
    }

    static long binarySearch(int start, int end) {
        long answer = Long.MAX_VALUE;

        while (start <= end) {
            int y = (start + end) / 2;
            long cost1 = calCost(y);
            long cost2 = calCost(y+1);
            if(cost1 > cost2){
                // 오른쪽 지점으로 이동했을 때 더 비용이 작다면 => 우측 탐색(좌측 버림)
                start = y+1;
            }else{
                end = y-1;
            }

            answer = Math.min(answer, cost1);
        }

        return answer;
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        barns = new int[N];
        prefix = new long[1000002];
        suffix = new long[1000002];

        // 헛간 위치 입력
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            barns[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(barns);

        // 구간합 입력
        int idx = 0;
        for(int i=0; i<1000001; i++){
            if(i!=0) prefix[i] = prefix[i-1] + idx;

            while(idx<N && barns[idx]==i) idx++;
        }

        int idx2 = N-1;
        for(int i=1000000; i>=0; i--){
            suffix[i] = suffix[i+1] + N - idx2 -1;

            while(idx2>=0 && barns[idx2]==i) idx2--;
        }


        Q = Integer.parseInt(br.readLine());
        while(Q-->0){
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());

            sb.append(binarySearch(0, 1000000)+"\n");
        }


        System.out.println(sb);
    }
}​