結果

問題 No.609 Noelちゃんと星々
ユーザー @abcde
提出日時 2019-06-22 22:50:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,364 bytes
コンパイル時間 3,176 ms
コンパイル使用メモリ 168,976 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-26 10:17:53
合計ジャッジ時間 3,710 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

// ロジック検討中.
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL MAX = 1e9;

int main() {
    
    // 1. 入力情報取得.
    LL N;
    scanf("%llu", &N);
    LL Y[N];
    for(int i = 0; i < N; i++) scanf("%llu", &Y[i]), Y[i] += 1e9;

    // 2. 昇順sort.
    sort(Y, Y + N);
    
    // 3. Noelちゃんが動かす必要のある距離の総和の最小値 を 計算する.
    // -> 二分探索で, opt を 探す
    LL hi = Y[N - 1];
    LL lo = Y[0];
    LL opt = 1 + (hi + lo) / 2;
    LL dist = 1e14, cur = 0;
    int counter = 0;
    // 無限ループ防止のため, カウンター入れる.
    while(counter < 100){
        
        // 3-1. 移動距離を保存.
        cur = 0;
        for(int i = 0; i < N; i++) cur += abs(opt - Y[i]);
        
        // 3-2. hi, lo, opt 更新.
        // cout << " hi=" << hi << " lo=" << lo << " opt=" << opt << endl;
        if(cur < dist) hi = (lo + hi) / 2LL;
        else           lo = (lo + hi) / 2LL;
        opt = 1 + (hi + lo) / 2;
        
        // 3-3. カウンター を インクリメント.
        counter++;
        
        // 3-4. 最小移動を距離更新.
        dist = min(dist, cur);
        
        // 3-5. 終了.
        if(hi - lo <= 0) break;
        
    }
    
    // 4. 出力.
    printf("%llu\n", dist);
    return 0;
    
}
0