に石を敷く

Description

[この問題は精度と効率テストで1点ずつ占めています]
ココ小学校のニニニズさんたちは、ライアン先生と一緒に秋の旅行に行ったとき、足場の石のある小川に出会って、向こうへ行くつもりだった.ライアン先生は、ニニニズの友达に安全に足場の石橋を渡るようにルールを作った.
マット石は一列のマット石からなり、各マット石には数字があり、マット石の数字は踏むたびに1減少します.
マット石の数が0の場合、これ以上踏み込むことはできません.この場合、次のマット石を使用して複数の格子を一度にスキップすることができます.
しかし、踏み石が複数ある場合は、無条件に最寄りの踏み石に飛び込むしかない.
ニニニズの友达は小川の左側にいて、小川の右の向こうに着いてこそ、石橋を渡ったことを認めた.
ニニニズの友达は一度に一人で石橋を渡り、一人の友达が石橋を渡った後、次の友达が歩き始めました.
パラメータとして一度にスキップできるマット石の最大格子数kを与える場合は、solution関数を完了し、最大何人まで越えることができるマット石を返します.
[制限]
橋を渡る必要があるNINIZの友達の数は無制限だと思います.
stores配列のサイズは1または200000以下です.
stone配列の各要素の値は1または2000000以下です.
kは1以上の石の長さ未満の自然数である.

Example

stones
[2, 4, 5, 3, 2, 1, 4, 2, 5, 1]
k = 3
result = 3
I/O例#1
最初の友達は石橋を通ることができます.

最初の友人が石橋を渡った後、ベンチの数字は下図のようになっています.
2番目の友達も石橋を通ることができます.下図のように.

2人目の友人が石橋を渡った後、足を踏み入れた数字は下図のようになっています.
3人目の友達も石橋を通ることができます.下図のように.

3人目の友人が石橋を渡った後、足を踏み入れた数字は下図のようになっています.
4番目の友达は石橋を渡るには、3番目の階段から7番目の階段に飛び込んで、4節を踊ります.しかし、k=3なのでスキップすることはできません.

そのため、最大3人がすべての敷石を通り抜けることができます.

Code

#include <bits/stdc++.h>

using namespace std;

bool check(vector<int> stones, int mid, int k){
    int cnt = 0;
    for(int i=0; i<stones.size(); i++){
        if(stones[i] < mid)
            cnt += 1;
        else
            cnt = 0;
        if(cnt == k){ // Can't pass
            return false;
        }
    }
    return true;
}

int solution(vector<int> stones, int k) {
    int answer = 0;
    int max_stone = *max_element(stones.begin(), stones.end());
    int min_stone = *min_element(stones.begin(), stones.end());
    while(max_stone>min_stone)
    {
        if(max_stone == min_stone+1){
            if(check(stones, max_stone, k) == true){
                answer = max_stone;
                break;
            }
            answer = min_stone;
            break;
        }
        int mid_stone  = (max_stone + min_stone)/2;
        if(check(stones, mid_stone, k) == true)
            min_stone = mid_stone;
        else
            max_stone = mid_stone-1;
    }
    if(max_stone==min_stone)
        answer = min_stone;
    return answer;
}

Thoughts

この問題は2019年のKakao冬季実習コードテストの最後の問題で、初めて問題を見ると「できるはずだ」と思っていましたが、精度や効率を考えると、決して簡単ではありません.単純に考えると、すぐに時間を超えてしまいます.
岩に書いてある値を一つ一つ減算して、人口ゼロがk個に達する瞬間まで、これはあまりにも非効率だと思い、新しい方法を考え出し、バイナリ探索を応用しました.
この問題で、正確に把握しなければならないのは、すべての岩の数字の中で、最大の数字+1の人は通過できないことだ.
それを把握しておけば、通過できる人数で「岩の最小値、岩の最大値」の範囲がわかります.
最小,最大値を知る場合,最も容易に実現できるのがバイナリ探索であり,時間的複雑度はO(logn)であるため有効な方法である.
従って、最小、最大中間値mid stoneの値を求め、mid stoneの場合(通行人がmid stoneの2人目の場合)に、通行可能か否かを知ることができる.
通れない場合は、新しい最大値をmidstone-1に設定し、通れる場合は、新しい最小値をmidstoneに設定して繰り返し、[min,max]値はex[n,n]OR[n,n+1と同じ形式に収束します.
[n,n+1]の場合,一人一人がもう一度チェックすれば正解が得られる.
整理する場合は、与えられた場合に最大値を探す必要がありますが、探している範囲を見つけることができるかどうか、最小と最大の状況を見つけることができれば、バイナリ検索を試して、欲しい最大状況を得ることができます.
困難🧐