問題

要約

長さNの数列A = (A1, A2, ..., AN)が与えられる。
「操作」は以下の手順で行われる：
- 1 ≤ i ≤ N を満たす整数 i を選択。
- 以下の2つのうちどちらかを選んで実行
  a) Ai に 1 を加算する。
  b) Ai から 1 を減算する。
Q個の質問に答える。
i番目の質問
- 「操作」を0回以上何度でも使って、数列Aの全ての要素をXiにするために必要な「操作」の最小回数を求める。

N: 数列Aの長さ
A = (A1, A2, ..., AN): 与えられる数列
Q: 質問の数
Xi: i番目の質問で、数列Aの全ての要素をこの値にする

既存投稿一覧ページへのリンク

一覧ページ

独り言

具体例

N = 5, A = [1, 3, 5, 7, 9], X = 6

累積和の計算

まず、Aの累積和CSを計算：
CS = [1, 4, 9, 16, 25]

二分探索

Xが6なので、二分探索を使ってAの中で6が入るべき位置を見つける。
この場合、インデックス2（値5）とインデックス3（値7）の間になる。

操作回数の計算

Aの要素を全て6にするために必要な操作回数を計算。

X以下の要素（1, 3, 5）に対する操作

必要な操作回数 = X * (idx + 1) - CS[idx]
= 6 * 3 - 9 = 9

Xより大きい要素（7, 9）に対する操作

必要な操作回数 = CS[N-1] - CS[idx] - X * (N - idx - 1)
= 25 - 9 - 6 * 2 = 4

合計操作回数

9 + 4 = 13

X以下の要素

これらの要素をXにするには、それぞれの要素を増やす必要がある。
全てをXにした場合の合計（6 * 3）から、現在の合計（CS[idx] = 9）を引くことで、必要な増加量（つまり操作回数）が分かる。

Xより大きい要素

これらの要素をXにするには、それぞれの要素を減らす必要がある。
現在の合計（CS[N-1] - CS[idx] = 25 - 9 = 16）から、全てをXにした場合の合計（6 * 2）を引くことで、必要な減少量が分かる。

解法手順

入力を受け取る（N, Q, A）。
数列Aをソートする。
Aの累積和（cs）を計算する。
各質問に対して以下の処理を行う：
a. 目標値Xiを入力として受け取る。
b. 二分探索関数（Nibutan）を使用して、Xi以下の最大の要素のインデックス（idx）を求める。
c. idxの値に応じて、以下の3つの場合に分けて操作回数を計算する：
- idx が -1 の場合（全ての要素がXiより大きい）
- idx が N の場合（全ての要素がXi以下）
- それ以外の場合（Xiより小さい要素と大きい要素が混在）
  d. 計算した操作回数を結果リスト（ans）に追加する。
全ての質問に対する結果を出力する。

ACコード

ac.py

def Nibutan(x, n_list):
    length = len(n_list)
    ok = 0
    ng = length - 1
    if n_list[0] > x:  # xが最小値より小さい場合
        return -1
    if n_list[-1] < x:  # xが最大値より大きい場合
        return length
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if n_list[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok

def io_func():
    # 入力を受け取る
    N, Q = map(int, input().split())  # 数列の長さNと質問の数Q
    A = list(map(int, input().split()))  # 数列A
    return N, Q, A

def solve(N, Q, A):
    A.sort()  # 数列Aをソート

    # 累積和を計算
    cs = [0] * N
    for i in range(N):
        if i == 0:
            cs[0] = A[0]
        else:
            cs[i] = cs[i-1] + A[i]

    ans = []
    for _ in range(Q):
        X = int(input())  # 目標値X
        idx = Nibutan(X, A)  # 二分探索でXの位置を特定

        if idx == -1:  # Xが最小値より小さい場合
            ans.append(cs[N-1] - X*N)
        elif idx == N:  # Xが最大値より大きい場合
            ans.append(X*N - cs[N-1])
        else:  # Xが最小値と最大値の間にある場合
            sum1 = -cs[idx] + X * (idx+1)
            sum2 = cs[N-1] - cs[idx] - X * (N - idx - 1)
            ans.append(sum1 + sum2)

    # 結果を出力
    for result in ans:
        print(result)

# メイン処理
N, Q, A = io_func()
solve(N, Q, A)

###
# - N: 数列Aの長さ
# - Q: 質問の数
# - A: 元の数列
# - cs: 累積和を格納するリスト
# - X: 各質問での目標値
# - idx: 二分探索で求めたXの位置
# - ans: 各質問に対する答えを格納するリスト

# 1. 入力処理（io_func関数）
#    - 数列の長さNと質問の数Qを受け取る
#    - 数列Aの要素を受け取る
# 2. 主処理（solve関数）
#    - 数列Aをソートする
#    - 累積和csを計算する
#    - 各質問に対して以下の処理を行う：
#      a. 目標値Xを入力として受け取る
#      b. 二分探索（Nibutan関数）を用いて、X以下の最大の要素のインデックスを求める
#      c. 求めたインデックスを基に、3つの場合に分けて最小操作回数を計算する
#    - 各質問の結果を出力する
# 3. 二分探索（Nibutan関数）
#    - ソートされた数列に対して、指定された値x以下の最大の要素のインデックスを返す
#    - xが最小値より小さい場合は-1を、最大値より大きい場合はリストの長さを返す