結果

問題 No.837 Noelちゃんと星々2
ユーザー lam6er
提出日時 2025-03-31 17:24:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 323 ms / 2,000 ms
コード長 1,370 bytes
コンパイル時間 149 ms
コンパイル使用メモリ 82,368 KB
実行使用メモリ 95,132 KB
最終ジャッジ日時 2025-03-31 17:25:16
合計ジャッジ時間 6,051 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

n = int(input())
y = list(map(int, input().split()))
y.sort()

prefix = [0] * (n + 1)
for i in range(n):
    prefix[i+1] = prefix[i] + y[i]

min_total = float('inf')

for k in range(1, n):
    left_size = k
    right_size = n - k

    left_median_pos = (left_size - 1) // 2
    left_median = y[left_median_pos]

    right_median_pos = k + ((right_size - 1) // 2)
    right_median = y[right_median_pos]

    left_candidates = [left_median - 1, left_median, left_median + 1]
    right_candidates = [right_median - 1, right_median, right_median + 1]

    for a in left_candidates:
        # Calculate sum_move_left for left group [0..k-1]
        pos = bisect.bisect_left(y, a, 0, k)
        sum_left_part = a * pos - (prefix[pos] - prefix[0])
        sum_right_part = (prefix[k] - prefix[pos]) - a * (k - pos)
        sum_left = sum_left_part + sum_right_part

        for b in right_candidates:
            if a == b:
                continue

            # Calculate sum_move_right for right group [k..n-1]
            pos_r = bisect.bisect_left(y, b, k, n)
            sum_l = b * (pos_r - k) - (prefix[pos_r] - prefix[k])
            sum_r = (prefix[n] - prefix[pos_r]) - b * (n - pos_r)
            sum_right = sum_l + sum_r

            total = sum_left + sum_right
            if total < min_total:
                min_total = total

print(min_total)
0