Pythonで減少および再配置した後に最大要素を見つけるプログラム

arrという配列があるとします。これらの条件を満たすために、arrに対していくつかの操作を実行する必要があります-

• arrの最初の要素は1でなければなりません。

• 隣接する2つの要素間の絶対差は最大で1でなければなりません。

そして、2つの操作があります。これらの2つのタイプの操作は何度でも実行できます-

• arrの値を正の数よりも小さくします。

• arrの要素を任意の順序に再配置します。

与えられた条件を満たすための操作を実行した後、arrで可能な最大値を見つける必要があります。

したがって、入力がarr =[3,3,2,3,2]の場合、出力は3になります。これは、最後の要素を1に減らしてから、[1,2,3,3]のように再配置できるためです。 、3]、最大は3です。

これを解決するには、次の手順に従います-

• リストを並べ替える

• arr [0]：=1

• 範囲1からarr-1のサイズのiの場合、実行します

  • arr [i]：=最小値（arr [i-1] + 1）およびarr [i]

• arrの最大値を返す

例

理解を深めるために、次の実装を見てみましょう-

def solve(arr):
   arr.sort()
   arr[0] = 1

   for i in range(1, len(arr)):
      arr[i] = min(arr[i - 1] + 1, arr[i])

   return max(arr)

arr = [3,3,2,3,2]
print(solve(arr))

入力

[3,3,2,3,2]

出力

3