[Programmers]外壁のチェック

これはすべての円形の外壁を検査するのに必要な最小の人力の問題です.
自分で作ったときにどうしても思い出せないので、他人が書いたブログを参考にしました.
トラブルシューティングポリシー
円形の外壁をチェックします.円形なので、2つの点の間の距離は方向によって異なります.
両方向の距離を両立させるために、本来は円形の壁を一字に並べて長さを倍にし、既存の場所に元の長さを加えて表示すればよい.


問題の円形の壁が一文字に展開され、両方の方向を考慮すると、最初の直線が現れます.
すべて羊水で置き換えられており、2番目の直線と考えられます.
補修が必要な場所がk個である場合,置換した直線上で連続したk個の場所を補修すれば完成する.
今は修理が必要な人を選ぶしかありません.
選定順も重要です.4メートルと2メートルを処理できる人がいると言ってください.
4、2の順に選択すると、10-13と17-18を担当し、すべての外壁の修理を完了できます.
ただし、2、4順に選定されていると、2名だけでは修理できません.
上の例のように、誰を選ぶかは重要ですが、順番を選ぶことも重要です.
したがって、シーケンスを使用して、どの順序で動作するかを指定できます.
仕事の順番を決めて、投入する人員が一番少ない人を見つければいいです.
コード#コード#

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<int> weak, vector<int> dist) {
    int answer = -1;
    
    vector<int> v;
    v = weak;
    for(int i=0;i<weak.size();i++)
        v.push_back(weak[i] + n);
    
    sort(dist.begin(), dist.end());
    
    do{
        for(int i=0;i<weak.size();i++){
            int start = v[i];
            int end = v[i+weak.size()-1];
            for(int j=0;j<dist.size();j++){
                start += dist[j];
                if(start >= end){
                    if(answer == -1)
                        answer = j+1;
                    else
                        answer = min(answer, j+1);
                    break;
                }
                
                int next = -1;
                for(int k = i+1;k<v.size();k++){
                    if(v[k] > start){
                        next = k;
                        break;
                    }
                }
                if(next != -1)
                    start = v[next];
                else
                    break;
            }
        }
    }while(next_permutation(dist.begin(), dist.end()));
    
    return answer;
}

補足すべき点
次の場所(next)を探していると、繰り返し文で見つかりました->O(n)
二分探索で次の場所を探せば、もっと短い時間で見つけることができます->O(logN)
upper bound(開始、終了、検索値)で二分ナビゲーションできます.
upper boundは、値が検索する値より大きい最初の場所を検索するために使用され、値の有無を検索するのではなく、値を挿入する場所を検索するために使用できます.
リファレンス
https://yjyoon-dev.github.io/kakao/2021/01/04/kakao-wallcheck/
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=occidere&logNo=221045300639
ソース
https://programmers.co.kr/learn/courses/30/lessons/60062#