結果

問題 No.837 Noelちゃんと星々2
コンテスト
ユーザー FromBooska
提出日時 2023-03-18 18:14:28
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,284 bytes
コンパイル時間 292 ms
コンパイル使用メモリ 81,900 KB
実行使用メモリ 269,952 KB
最終ジャッジ日時 2024-09-18 13:27:30
合計ジャッジ時間 7,454 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

ans = 10**10
from math import floor, ceil
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)
0