白駿11497.丸木をスキップ-解答(Python/Python)


🔎 11497号です.質問の表示
https://www.acmicpc.net/problem/11497

💡 問題を解く前に
今日の教訓は、文章が多いからといって変な絵があるのを恐れるのではなく、順を追って近づいていくこと...!😉💪 探しているルールは予想以上に簡単です!
📋 コードの表示
from sys import stdin

for i in range(int(stdin.readline())):
    X = int(stdin.readline())
    nums = sorted(list(map(int, stdin.readline().split())))
    level = 0
    for j in range(2, X):
        level = max(level, abs(nums[j] - nums[j - 2]))
    print(level)
🥕 コード解釈と関連概念

問題を解く構想.


目標は難易度を最も容易にします!
実際、一般的には、昇順または降順に並べば、最大の車が出力され、これは難易度であり、ここで条件が追加されます.
1本目と最後の1本が隣接しています.
すなわち,[1,3,5,6,8]を用いると,この配列の難易度も|8−1|=7となる.
だから考えて、最大の数を真ん中に集中して、両側を散らすと、数が少なくなります!そんな思いを思い出した.
上記の例に従って操作すると、
[ ?, ?, 8, ?, ? ] 冒頭でいいです.
今は両側に数を減らすべきですが、ここではどんな基準で減らすのでしょうか.これは私を長い間悩ませた.
まず8の両側に8に一番近い手を置きます.(右から来ても左から来ても、実はひっくり返しても同じで、気にしません.
[ ?, 6, 8, 5, ? ]
うん.ここで難易度を最小限に抑えるには、残りの数でさらに数を増やさなければなりません!
この例では、8の後に大きな数(6)があり、左側にあるので左側で始まると思います.
[ 3, 6, 8, 5, 1 ]
完成!
これはコードで実現される部分です.
for j in range(2, X):
        level = max(level, abs(nums[j] - nums[j - 2]))
ここ
他の例が適用されても完了します.
[1,3,5,6,8]の場合
1 - 5
3 - 6
このように接続されているので、上のようにコードを作ると、計算が自動的にミスマッチします!