問題情報

問題の説明

問題の概要

命令配列が与えられた場合、空容器numsに左から右にinstructを挿入すると、挿入コストの最小和が求められる.ただし、最小料金が非常に大きくなる可能性がありますので、10^9+7に分かれた残りの分を返却してください.
各挿入の最小コストは、次の方法で行います.

は現在numsで命令[i]より小さい数を厳密に求めている.

は現在numsで命令[i]より大きい数を厳密に求めている.

例えばnums=[1,2,3,5]に3を挿入するとすると、挿入コストはmin(2,1)となる.(1および2は3未満、5は3より大きい)従ってnumsは[1,2,3,5]である.

こうそくじょうけん

1 <= instruction.length <= 10^5

1 <= instructions[i] <= 10^5

質問へのアクセス

命令を入力するたびにnums配列の中の厳密さが自分より小さい数とnums配列の中の厳密さが自分より大きい数という点からバイナリ検索(binary search)で解けばいいと思います.
これは基本的なbinary searchのさらなる問題であり,Pythonの対分モジュールを利用すれば解決できる.Pythonの分割モジュールの使用を避けるため,swiftは分割leftの解を実施した.
分割leftに対して同じサイズの数字を返す場合の一番左側の位置、同じサイズの数字を返す場合の一番右側の位置.対分leftと対分を用いると、現在numsにおける命令[i]より小さい個数は対分leftを得る値であり、命令[i]より大きい個数は現在nums長iから対分を減算した値で得られる.

class Solution:
    def createSortedArray(self, instructions: List[int]) -> int:
        answer = 0
        arr = []
        n = len(instructions)
        MOD = 10 ** 9 + 7
        for i, inst in enumerate(instructions):
            l = bisect.bisect_left(arr, inst)
            r = bisect.bisect(arr, inst)
            answer += min(l, i - r)
            arr[r:r] = [inst]
        return answer % MOD