[白俊]3020号:ホタル

30214 ワード
テキストリンク
3020号:ホタル
区間は高さ1単位で区切られています.
上の長さと下の長さ
タケノコリスト(下で育った)
鍾乳石リスト

最初のプール:バイナリナビゲーション:low boundの使用


lower bood(k):kの初期インデックス以上を求める方法
  • 通常できない場合はlistの長さ(インデックスがlistの長さを返すことができない数)
    • を返します.
    タケノコと鍾乳石をそれぞれ二分探索すべきである.
    したがって
    6 7
1
5
3
3
5
1
    石筍
    鍾乳石
    実際、高さ2の区間ではタケノコが2で、鍾乳石ならh-2を考えます.
  • 修正→そう考えると間違いです.h-2+1にしたい.
  • 高さが2の場合、区間は最終的に第2の線と第3の線の間にあるため、
    • 0からhが私の高さの時、
    タケノコリストから下限(x)を求め,鍾乳石リストから下限(h−x+1)を求める.
  • 下限(x):x以上の最小インデックスを表します.→バイナリ検索でこれを求めるのでO(logn)時間が必要です.
  • 50万x O(logn)なので、時間の複雑さに問題はないはずです
    • import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
    public static int n,h;
    public static int[] low,high;
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;
    public static int min=Integer.MAX_VALUE;
    public static int cnt=0;
    public static void setting() throws IOException{
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());
        // n은 항상 짝수
        int len = n/2;
        low = new int[len];
        high = new int[len];
        for(int i=0;i<len;i++){
            low[i] = Integer.parseInt(br.readLine());
            high[i] = Integer.parseInt(br.readLine());
        }
    }
    public static void solve(){
        Arrays.sort(low);// 오름차순
        Arrays.sort(high);// 오름차순

        int sum=0;
        int idx=0;
        for(int height=1;height<=h;height++){
            sum=0;
            idx = lower_bound(low,height);
            sum+=(low.length-idx);
            idx = lower_bound(high,h-height+1);
            sum+=(high.length-idx);
            if(sum<min){
                min=sum;
                cnt=1;
            }
            else if(sum==min) cnt++;
        }
    }
    // target보다 크거나 같은 것 중 가장 작은 것의 index를 리턴한다.
    // 없을 경우 list.length를 리턴한다.
    public static int lower_bound(int[] list,int target){
        int left =0,right=list.length;
        int mid = 0;
        while(left<right){
            mid = (left+right)/2;
            if(list[mid]>=target)right = mid;
            else left = mid+1;
        }
        return right;
    }
    public static void main(String[] args) throws IOException {
        setting();
        solve();
        System.out.println(min+" "+cnt);
    }
}

    他者解答：累計加算


    高さによってタケノコ、鍾乳石を貯蔵する個数.
    low[h]=個数
    high[何h]=個数
    その後、タケノコのリストを見てみましょう.
    6 7

1
5
3
3
5
1
인 경우 현재 석순 리스트는 
h  1 2 3 4 5 6 
	 1 0 1 0 1 0
    今は累積を利用すればいいです.
  • タケノコ[h]現在は高さhより大きいタケノコの個数を貯蔵するだけである.==累積集計が行われます
  • このとき注意して、後から積み重ねる.なぜなら、hが4のタケノコは、タケノコ[0]、タケノコ[1]、タケノコ[2]、タケノコ[3]に蓄積すべきであり、
    • package coding;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
    public static int n,h;
    public static int[] low,high;
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;
    public static int min=Integer.MAX_VALUE;
    public static int cnt=0;
    public static void setting() throws IOException{
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());
        // n은 항상 짝수
        int len = n/2;
        low = new int[h+1];
        high = new int[h+1];
        for(int i=0;i<len;i++){
            low[Integer.parseInt(br.readLine())]++;
            high[Integer.parseInt(br.readLine())]++;
        }

    }
    public static void solve() {
        // 높이가 4인 종유석은 높이 1을 포함하고 있는 것이니, 뒤에서부터 누적
        for(int height =h-1;height>=0;height--){
            low[height]+=low[height+1];
            high[height]+=high[height+1];
        }
        
        int sum=0;
        for(int height=1;height<=h;height++){
            sum=0;
            sum+=low[height];
            sum+=high[h-height+1];
            if(sum<min){
                min = sum;
                cnt=1;
            }else if(sum==min){
                cnt++;
            }
        }

    }
    public static void main(String[] args) throws IOException {
        setting();
        solve();
        System.out.println(min+" "+cnt);
    }
}
    カスタムアダプタ
    [BOJ][9663] N-Queen