[Programmers]外壁のチェック


🔦 提问链接


▼▼▼▼草


ポイントはレストランが丸いことです.
円なので、起点がどこであれ、すべての場所を通ることができます.
したがって、弱い点を任意の位置から開始するために1周後に拡張します.
  • weak.append(weak[i]) for i in range(length)
  • まず、どの場所からアクセスを開始するかを決定します.選択可能なアクセス先はすべての場所ですが、弱点からは常に最適です.私たちは弱い部分から一つを選んだ.
    第二に、友达が持つことができる順番の中の1つを選んで、それから友达を選びます.
    最初に選択した起点と友人の距離を加算すると、最大の距離を求めることができます.
    3つ目は、脆弱点がどこまで覆われているかを確認することです.
    2番目に求めた最大距離を起点の脆弱点を考慮した距離と比較し,脆弱点がもっと遠ければ友人を追加し,友人の距離に応じて最大距離を増やす.最大距離がさらに遠くなると、次の弱点も上書きできるかどうかを確認します.このとき,友人の数が規定の数を超えると,すべての弱点を隠すことができない.

    🛠 コード#コード#

    from itertools import permutations
    def solution(n, weak, dist):
        answer = 0
        length = len(weak)
        for i in range(length):
            weak.append(weak[i] + n)
        mn = len(dist) + 1
        
        for start in range(length):
            for per in list(permutations(dist, len(dist))):
                count = 1
                distance = weak[start] + per[count - 1]
                for i in range(start, start + length):
                    if distance < weak[i]:
                        count += 1
                        if count > len(dist):
                            break
                        distance = weak[i] + per[count - 1]
                        
                    
                mn = min(mn, count)
        if mn > len(dist):
            return -1
        return mn

    📝 整理する

  • の特性-どこからでもすべての場所を通過できる.
  • 🎈 リファレンス