結果
問題 | No.837 Noelちゃんと星々2 |
ユーザー |
![]() |
提出日時 | 2023-06-03 18:46:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 118 ms / 2,000 ms |
コード長 | 1,920 bytes |
コンパイル時間 | 178 ms |
コンパイル使用メモリ | 82,848 KB |
実行使用メモリ | 101,052 KB |
最終ジャッジ日時 | 2024-12-29 03:13:23 |
合計ジャッジ時間 | 4,002 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
# まずYを昇順ソート # 2個のmedian, 中央値を作ってそこに寄せればいい # どこからを2グループ目とするかで全探索 # medianまでの距離の和は、median後の要素の和 - median前の要素の和 # つまり累積和で高速化できる、はず N = int(input()) Y = list(map(int, input().split())) Y.sort() cumu = [0] temp = 0 for i in range(N): temp += Y[i] cumu.append(temp) ans = 10**20 for second in range(1, N): #print(second, Y[second]) first_len = second second_len = N - first_len first_sum = cumu[second] second_sum = cumu[N]-first_sum #print(first_len, second_len, first_sum, second_sum) if first_len%2 == 0: first_median = (Y[first_len//2-1]+Y[first_len//2])//2 else: first_median = Y[first_len//2] if second_len%2 == 0: second_median = (Y[first_len+second_len//2-1]+Y[first_len+second_len//2])//2 else: second_median = Y[first_len+second_len//2] #print('first_median', first_median, 'second_median', second_median) # medianまでの距離の和は、median後の要素の和 - median前の要素の和 if first_len%2 == 0: first_distance = (cumu[first_len]-cumu[(first_len+1)//2])-(cumu[(first_len+1)//2]-cumu[0]) else: first_distance = (cumu[first_len]-cumu[(first_len+1)//2])-(cumu[(first_len+1)//2-1]-cumu[0]) if second_len%2 == 0: second_distance = (cumu[first_len+second_len]-cumu[(second_len+1)//2+first_len])-(cumu[(second_len+1)//2+first_len]-cumu[0+first_len]) else: second_distance = (cumu[first_len+second_len]-cumu[(second_len+1)//2+first_len])-(cumu[(second_len+1)//2-1+first_len]-cumu[0+first_len]) ans = min(ans, first_distance+second_distance) if Y[0] == Y[N-1]: # 全部おなじときはグループ1を1要素にして違うmedianにすれば1が達成可能 print(1) else: print(ans)