Pythonの有界配列の特定のインデックスで最大値を見つけるプログラム

n、index、maxSumの3つの値があるとします。 nums [index]を見つける必要があるnumsという配列を考えてみましょう。また、numsは次の条件を満たす必要があります-

• numsのサイズはnです

• nのすべての要素は正です。

• | nums [i]-nums [i + 1] | <=1すべてのi、0 <=i

• numsのすべての要素の合計がmaxSumを超えない。

• nums[index]が最大化されます。

したがって、入力がn =6、index =3、maxSum =8の場合、出力は2になります。これは、[1,2,2,2,1,1]のような、すべてを満たす配列を取得できるためです。条件、ここではnums[3]が最大化されます。

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

• 左：=maxSum / nの商、右：=maxSum + 1

• ans：=0

• 左<右、する

  • mid：=左+（右左）/2の商

  • ind_l：=（mid-1 +最大1および（mid-index））*（インデックスの最小値および（mid-1）/ 2 + |最小値0、mid-index-1 |

    の商

  • ind_r =（mid +最大1および（mid-（n-index-1）））*（（n-index）の最小値およびmid）/ 2 + | 0の最小値および（mid-（n-index））の商-1）-1）|

  • ind_l + ind_r <=maxSumの場合、

    • ans：=mid

    • 左：=mid + 1

  • それ以外の場合

    • 右：=半ば

• ansを返す

例

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

def solve(n, index, maxSum):
   left, right = maxSum//n, maxSum+1
   ans = 0
   while(left<right):
      mid = left + (right-left)//2
      ind_l = (mid-1+max(1,mid-index))*min(index,mid-1)//2 + abs(min(0,mid-index-1))
      ind_r = (mid+max(1,mid-(n-index-1)))*min(n-index, mid)//2+ abs(min(0,mid-(n-index-1)-1))

      if ind_l + ind_r <=maxSum:
         ans = mid
         left = mid+1
      else:
         right = mid
   return ans

n = 6
index = 3
maxSum = 8
print(solve(n, index, maxSum))

入力

6, 3, 8

出力

2