結果

問題 No.609 Noelちゃんと星々
ユーザー @abcde@abcde
提出日時 2019-06-22 22:57:43
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,405 bytes
コンパイル時間 2,196 ms
コンパイル使用メモリ 168,840 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-26 10:18:13
合計ジャッジ時間 3,901 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
権限があれば一括ダウンロードができます

ソースコード

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