結果
問題 | No.609 Noelちゃんと星々 |
ユーザー | @abcde |
提出日時 | 2019-06-22 22:57:43 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,405 bytes |
コンパイル時間 | 1,798 ms |
コンパイル使用メモリ | 168,780 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-07 23:16:26 |
合計ジャッジ時間 | 2,676 ms |
ジャッジサーバーID (参考情報) |
judge4 / 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 | - |
ソースコード
// ロジック検討中. #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; }