結果

問題 No.837 Noelちゃんと星々2
ユーザー FromBooskaFromBooska
提出日時 2023-03-18 19:14:09
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,832 bytes
コンパイル時間 187 ms
コンパイル使用メモリ 81,832 KB
実行使用メモリ 91,152 KB
最終ジャッジ日時 2023-10-18 17:27:47
合計ジャッジ時間 3,748 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 123 ms
90,872 KB
testcase_01 WA -
testcase_02 AC 123 ms
90,872 KB
testcase_03 AC 127 ms
90,872 KB
testcase_04 AC 123 ms
91,136 KB
testcase_05 AC 123 ms
90,872 KB
testcase_06 AC 123 ms
91,136 KB
testcase_07 AC 122 ms
90,872 KB
testcase_08 AC 123 ms
90,872 KB
testcase_09 AC 45 ms
61,864 KB
testcase_10 AC 37 ms
53,800 KB
testcase_11 AC 39 ms
53,800 KB
testcase_12 AC 36 ms
53,800 KB
testcase_13 AC 37 ms
53,800 KB
testcase_14 AC 44 ms
61,736 KB
testcase_15 AC 45 ms
61,864 KB
testcase_16 AC 36 ms
53,800 KB
testcase_17 AC 42 ms
59,664 KB
testcase_18 AC 37 ms
53,800 KB
testcase_19 AC 37 ms
53,800 KB
testcase_20 AC 47 ms
59,684 KB
testcase_21 AC 46 ms
61,864 KB
testcase_22 AC 45 ms
61,864 KB
testcase_23 AC 41 ms
59,664 KB
testcase_24 AC 37 ms
53,736 KB
testcase_25 AC 36 ms
53,800 KB
testcase_26 AC 36 ms
53,800 KB
testcase_27 AC 37 ms
53,800 KB
testcase_28 AC 37 ms
53,800 KB
testcase_29 AC 37 ms
53,800 KB
testcase_30 AC 39 ms
53,800 KB
testcase_31 AC 38 ms
53,800 KB
testcase_32 AC 36 ms
53,800 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# これが1種類にまとめるのであればmedianだろう
# ということはYをソートして、前から何個目までを1グループ目とするかで探索
# 1グループ目は1グループ目のmedianに、2グループ目は2グループ目のmedianに
# その最低値が答えか
# 二重ループでTLE
# 三分探索で最低値を探す

N = int(input())
Y = list(map(int, input().split()))
Y.sort()

from math import floor, ceil

def cost_calc(group1_len):
    group2_len = N - group1_len
    if group1_len%2 == 1:
        median1 = Y[group1_len//2]
    else:
        median1 = floor((Y[group1_len//2-1]+Y[group1_len//2])/2)
    if group2_len%2 == 1:
        median2 = Y[group1_len + group2_len//2]
    else:
        median2 = floor((Y[group1_len + group2_len//2-1]+Y[group1_len + group2_len//2])/2)
    if median2 == median1: 
        median2 += 1
    calc = 0
    for i in range(group1_len):
        calc += abs(Y[i]-median1)
    for i in range(group1_len, N):
        calc += abs(Y[i]-median2)
    return calc

if N < 100:
    ans = 10**20
    
    for group1_end in range(N-1):
        group1 = Y[:group1_end+1]
        group1_len = group1_end+1
        group2 = Y[group1_end+1:]
        group2_len = N - group1_len
        if group1_len%2 == 1:
            median1 = Y[group1_len//2]
        else:
            median1 = floor((Y[group1_len//2-1]+Y[group1_len//2])/2)
        if group2_len%2 == 1:
            median2 = Y[group1_len + group2_len//2]
        else:
            median2 = floor((Y[group1_len + group2_len//2-1]+Y[group1_len + group2_len//2])/2)
        if median2 == median1: 
            median2 += 1
        cost = 0
        for i in range(group1_len):
            cost += abs(Y[i]-median1)
        for i in range(group1_len, N):
            cost += abs(Y[i]-median2)
        ans = min(ans, cost)

        #print(group1, group2)
        #print(group1_len, group2_len, median1, median2, cost)
        #print()

    print(ans)
else:
    # 谷、つまり1極値を求める三分探索での解き方
    # https://roiti46.hatenablog.com/entry/2015/04/29/yukicoder_No.198_%E3%82%AD%E3%83%A3%E3%83%B3%E3%83%87%E3%82%A3%E3%83%BC%E3%83%BB%E3%83%9C%E3%83%83%E3%82%AF%E3%82%B9%EF%BC%92
    # https://qiita.com/ganyariya/items/1553ff2bf8d6d7789127

    # 範囲に注意、ギリギリありえない値とする
    left, right = 0, N-1
    while right-left > 2:
        left_mid, right_mid = (2*left+right)//3, (left+2*right)//3
        if cost_calc(left_mid) <= cost_calc(right_mid):
            # 右midの方が大きいから右を右midに変える
            right = right_mid
        else:
            left = left_mid

    #print(left_mid, right_mid)

    ans = min(cost_calc(left_mid), cost_calc(right_mid))
    # leftとrightの間も入れる必要あるのか?
    print(ans)
0