結果

問題 No.837 Noelちゃんと星々2
ユーザー FromBooskaFromBooska
提出日時 2023-06-03 18:46:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 144 ms / 2,000 ms
コード長 1,920 bytes
コンパイル時間 281 ms
コンパイル使用メモリ 86,952 KB
実行使用メモリ 100,920 KB
最終ジャッジ日時 2023-08-28 08:02:12
合計ジャッジ時間 5,878 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 140 ms
100,444 KB
testcase_01 AC 144 ms
100,528 KB
testcase_02 AC 139 ms
100,680 KB
testcase_03 AC 139 ms
100,516 KB
testcase_04 AC 141 ms
100,920 KB
testcase_05 AC 141 ms
100,500 KB
testcase_06 AC 141 ms
100,892 KB
testcase_07 AC 140 ms
100,624 KB
testcase_08 AC 138 ms
100,444 KB
testcase_09 AC 68 ms
71,344 KB
testcase_10 AC 67 ms
71,260 KB
testcase_11 AC 69 ms
71,408 KB
testcase_12 AC 69 ms
71,120 KB
testcase_13 AC 72 ms
71,104 KB
testcase_14 AC 69 ms
71,224 KB
testcase_15 AC 71 ms
71,256 KB
testcase_16 AC 69 ms
71,376 KB
testcase_17 AC 70 ms
71,208 KB
testcase_18 AC 71 ms
71,304 KB
testcase_19 AC 70 ms
71,108 KB
testcase_20 AC 69 ms
71,204 KB
testcase_21 AC 69 ms
71,452 KB
testcase_22 AC 71 ms
71,412 KB
testcase_23 AC 69 ms
71,228 KB
testcase_24 AC 69 ms
71,260 KB
testcase_25 AC 70 ms
71,344 KB
testcase_26 AC 71 ms
71,484 KB
testcase_27 AC 70 ms
71,272 KB
testcase_28 AC 70 ms
71,268 KB
testcase_29 AC 70 ms
71,352 KB
testcase_30 AC 69 ms
71,312 KB
testcase_31 AC 70 ms
71,452 KB
testcase_32 AC 70 ms
71,304 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# まず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)
0