【競技プログラミング】AtCoder Beginner Contest 255_D問題

# 問題
https://atcoder.jp/contests/abc255/tasks/abc255_d

## 要約
1. 長さNの数列A = (A1, A2, ..., AN)が与えられる。

2. 「操作」は以下の手順で行われる：
   - 1 ≤ i ≤ N を満たす整数 i を選択。
   - 以下の2つのうちどちらかを選んで実行
     a) Ai に 1 を加算する。
     b) Ai から 1 を減算する。

3. Q個の質問に答える。

4. i番目の質問
   - 「操作」を0回以上何度でも使って、数列Aの全ての要素をXiにするために必要な「操作」の最小回数を求める。

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


# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)


# 独り言
## 具体例
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）を引くことで、必要な減少量が分かる。


# 解法手順

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


# ACコード
```python: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を、最大値より大きい場合はリストの長さを返す
```