結果

問題 No.837 Noelちゃんと星々2
ユーザー ntuda
提出日時 2025-03-04 21:13:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 125 ms / 2,000 ms
コード長 992 bytes
コンパイル時間 529 ms
コンパイル使用メモリ 82,728 KB
実行使用メモリ 111,432 KB
最終ジャッジ日時 2025-03-04 21:14:02
合計ジャッジ時間 4,640 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import accumulate
N = int(input())
Y = list(map(int,input().split()))
if len(set(Y)) == 1:
    print(1)
    exit()
Y.sort()
for i in reversed(range(N)):
    Y[i] -= Y[0]

YA = list(accumulate(Y))
INF = 10 ** 15
'''
# をi未満のグループG1とi以上のグループG2に分ける
G1の中間となる頂点c1 = i//2
G2の頂点となる頂点c2 = i+(N-i)//2
G1を頂点1に集合させる距離の総和は
(c1 + 1) * Y[c1] - YA[c1]
+ YA[i-1] - YA[c1] - (i-c1-1) * Y[c1]
G1を頂点1に集合させる距離の総和は
(c2 - i + 1) * Y[c2] - (YA[c2] - YA[i-1])
+ YA[N-1] - YA[c2] - (N - c2 - 1) * Y[c2]
'''
ans = INF
for i in range(1,N):
    c1 = i//2
    c2 = i + (N-i)//2
    tmp11 = (c1 + 1) * Y[c1] - YA[c1]
    tmp12 = YA[i-1] - YA[c1] - (i-c1-1) * Y[c1]
    tmp21 = (c2 - i + 1) * Y[c2] - (YA[c2] - YA[i-1])
    tmp22 = YA[N-1] - YA[c2] - (N - c2 - 1) * Y[c2]
    ans = min(ans,tmp11+tmp12+tmp21+tmp22)
    #print(i,":",c1,c2,":",tmp11,tmp12,tmp21,tmp22)
print(ans)
0