s8pc_6_b

パッと見た瞬間,A[0]~A[n-1]の間のどこかに入り口があってB[0]~B[n-1]の間のどこかに出口がありそうってなる

最悪のケースで最左端から最右端の可能性もあるしなぁってなりながらもとりあえず2分探索書いてみたけどサンプル合わず

サンプルよく見てみると入り口と出口に必ずA[i]とB[i]が含まれてる事を発見

N個の中から入り口と出口を探してAC

#include<bits/stdc++.h>

using namespace std;

int n;

long long int a[33], b[33];

int main(){

    long long int sum = 0;

    cin >> n;

    for(int i=0;i<n;i++){

        int aa, bb;

        cin >> aa >> bb;

        if(aa < bb) a[i] = aa, b[i] = bb;

        else a[i] = bb, b[i] = aa;

        sum += abs(aa-bb);

    }

    long long int ax = 40000000000;

    long long int bx = 40000000000;

    for(int i=0;i<n;i++){

        long long int asum = 0;

        for(int j=0;j<n;j++){

            asum += llabs(a[i] - a[j]);

        }

        long long int bsum = 0;

        for(int j=0;j<n;j++){

            bsum += llabs(b[i]-b[j]);

        }

        ax = min(ax, asum);

        bx = min(bx, bsum);

    }

    cout << sum + ax + bx << endl;

}