ZeroJudge H084: Posters on the Wall

There is a fence made up of N wooden boards, each with heights H1, H2, ..., HN. There are K posters to be posted on the fence, each with widths W1, W2, ..., WK, and a height of 1.

If you want to post a poster at height X, then the ith poster needs to be placed on a continuous segment of wooden boards with a length of Wi, and each board in the segment should have a height of at least X. Additionally, the height at which each poster is placed must be consistent, follow the order, and not overlap (they can be adjacent). The question is asking for the maximum height at which you can place the posters.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
第一行有兩個正整數 N 和 K，接下來一行有 
N 個正整數代表每個木板的高度，最後一行有 K 個正整數代表每張海報的寬度。		輸出最大可以張貼的高度。
5 1
6 3 7 5 1
3		3
10 3
5 3 7 5 1 7 5 3 8 4
2 2 1		5

Sample Teat Case Explanation

Sample Test Case 2

ZeroJudge H084 範例測資圖文解說

柵欄長相如上圖，三張海報 (寬度為 2, 2, 1) 可以貼在高度為 5 的高度。

Thought Process

Store all heights in an array, ensuring there are no duplicate heights. Sort the array and then use binary search to retrieve the current height being evaluated.

取到現在要判斷的高度後，先從第一塊海報開始判斷，如果有連續且高度 >= 判斷高度的木板，則代表這塊海報放得上去，從下一塊木板開始判斷下一張海報。如果放不上去的話就是從下一塊木板開始判斷目前這張海報。

If all the posters can be placed at the current height, set the current height as the answer, and the next binary search will continue to the right. Otherwise, it will continue to the left. When the binary search terminates, it's necessary to re-evaluate whether the highest board can accommodate a poster because the binary search won't reach the last position.

Sample Code－ZeroJudge H084: Posters on the Wall

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, K;
    vector<int>num, height, poster;
    cin >> N >> K;
    map<int, int>MAP;
    for (int i = 0; i<N; i++)
    {
        int tmp;
        cin >> tmp;
        num.push_back(tmp);
        if (MAP[tmp] == 0) height.push_back(tmp);
        MAP[tmp]++;
    }
    for (int i = 0; i<K; i++)
    {
        int tmp;
        cin >> tmp;
        poster.push_back(tmp);
    }
    sort(height.begin(), height.end());
    int L = 0, R = int(height.size())-1, count = 0, ans = 1;
    while (true)
    {
        if (L >= R) break;
        count = 0;
        int query = height[(L+R)/2];
        for (int i = 0; i<N; i++)
        {
            if (num[i] >= query)
            {
                bool ok = true;
                if (i+poster[count] > N) continue;
                int j = i;
                for (j = i; j<i+poster[count]; j++)
                {
                    if (num[j] < query)
                    {
                        ok = false;
                        i = j;
                        break;
                    }
                }
                if (ok)
                {
                    count++;
                    i = j-1;
                }
            }
        }
        if (count >= K)
        {
            L = ((L+R)/2)+1;
            ans = query;
        }
        else R = ((L+R)/2);
    }
    int query = height[int(height.size())-1];
    count = 0;
    for (int i = 0; i<N; i++)
    {
        if (num[i] >= query)
        {
            bool ok = true;
            if (i+poster[count] > N) continue;
            int j = i;
            for (j = i; j<i+poster[count]; j++)
            {
                if (num[j] < query)
                {
                    ok = false;
                    i = j;
                    break;
                }
            }
            if (ok)
            {
                count++;
                i = j;
            }
        }
    }
    if (count >= K) ans = query;
    cout << ans << "\n";
    
}

//ZeroJudge H084
//Dr. SeanXD
Tags

Related Posts

Comments