阿祁的部落格

APCS 2022.1 P4 牆上海報 解題心得( 題目 )

解題概念:二分搜、Greedy

解題方法:我們先把問題簡化，把題目改成:「給你海報要掛的高度，問你可不可能掛上去?」，我們可以利用一件事，如果前面有個區間長度比我現在要張貼的還長，我可以選擇把我的海報放在這區的最左邊，這樣才有機會留更多空間給下一個，而其實我們透過一次O(n)就可以回答這個問題。

回到原本問題，我們可以透過這種方式檢查，但是我們當然不能分別試，我們發現海報掛越低越有機會成功(像是h=1一定成功)，所以發現其實具有單調性，我們可使用二分搜在1~10^9裡找一個可成功的最大值。因此總複雜度為O(nlogC)。

Java參考程式碼 (有更好意見可留言於下方，謝謝!)

//Author:En Chi Tsung(欉恩祁)

//Date:2022/1/9

import java.io.*;

import java.util.*;

import java.math.*;

public class zjh084 {

    public static int ret,r,n,k,lt,cnt;

    public static int[] h=new int[200005];//高度

    public static int[] t=new int[50005];//長度

    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception{

        n=readint();

        k=readint();

        for(int i=0;i<n;i++) {

            h[i]=readint();

        }

        for(int i=0;i<k;i++) {

            t[i]=readint();

        }

        System.out.println(BIS());

    }

    

    public static int BIS() {

        int L=1,R=1000000000,m;//二分搜

        while(L!=R) {

            m=(L+R+1)/2;

            if(TRY(m)) {

                L=m;

            }

            else {

                R=m-1;

            }

        }

        return L;

    }

    
 
    public static boolean TRY(int x) { //O(n)判斷可行性

        cnt=0;

        lt=-1;

        for(int i=0;i<n;i++) {

            if(h[i]<x) {

                lt=i;

            }

            else if(i-lt==t[cnt]) {

                lt=i;

                cnt++;

                if(cnt==k)break;

            }

        }

        if(cnt!=k)return false;

        return true;

    }

    

    public static int readint() throws Exception {

        ret=0;

        r=br.read();

        while(r>47&&r<58) {

            ret*=10;

            ret+=(r&15);

            r=br.read();

        }

        return ret;

    }

}