結果

問題 No.3268 As Seen in Toasters
コンテスト
ユーザー srjywrdnprkt
提出日時 2025-09-16 19:17:35
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 80 ms / 2,000 ms
コード長 1,790 bytes
コンパイル時間 3,632 ms
コンパイル使用メモリ 295,728 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-09-16 19:17:42
合計ジャッジ時間 6,787 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <atcoder/modint>

using namespace std;
//using namespace atcoder;
using ll = long long;
//using mint = modint998244353;

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    /*
       x>=0, y>=0でない限り隣接する絶対値の和を足す関数。
       よって、非負のものは隣接させた方が良い。
       非負の部分の両端は1回足され、
       負の部分は両端にない限りは2回足される。
       ここで非負の部分に注目すると階段状になっていればどんな並べ方をしても階差の絶対値の和は同じ
       あとは2パターンを探す。
       (1)負正負のパターン
       (2)負正のパターン
    */

    ll N, a, ans=9e18;
    cin >> N;
    deque<ll> neg, pos;
    for (int i=0; i<N; i++){
        cin >> a;
        if (a >= 0) pos.push_back(a);
        else neg.push_back(a);
    }
    sort(pos.begin(), pos.end());
    sort(neg.begin(), neg.end());

    if (!neg.empty()){
        ll sm=0;
        deque<ll> all;
        all.push_back(neg[0]);
        all.insert(all.end(), pos.begin(), pos.end());
        for (int i=neg.size()-1; i>=1; i--) all.push_back(neg[i]);
        for (int i=0; i<all.size()-1; i++){
            ll x = all[i], y = all[i+1];
            if (x < 0 && y < 0) sm += -x-y;
            else sm += abs(x-y);
        }
        ans = min(ans, sm);
    }
    ll sm = 0;
    deque<ll> all;
    all.insert(all.end(), neg.begin(), neg.end());
    all.insert(all.end(), pos.begin(), pos.end());
    for (int i=0; i<all.size()-1; i++){
        ll x = all[i], y = all[i+1];
        if (x < 0 && y < 0) sm += -x-y;
        else sm += abs(x-y);
    }
    ans = min(ans, sm);


    cout << ans << endl;

    return 0;
}
0