[BOJ/C++] 2405 - 세 수, 두 M

https://www.acmicpc.net/problem/2405

---

 

 

완전탐색으로 돌기에는.. n <= 100'000이라 분명히 시간초과가 날것이고, 뭔가 연산을 줄일만한 방법이 있을 것이다.

우선, 중위값과 평균값의 식을 잘 정리해보았고, 식을 통해 그리디하게 답을 구할 수 있었다.

 

 

ta-tb 또는 tc-tb를 최소화하려면 배열을 정렬했을때, 두 원소가 이웃하면되고,

반대로 최대화하려면 가장 멀리 떨어져있어야 한다.

 

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(int i=x;i<y;i++)
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*----------------------*/

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin>>n;
    vector<int> v(n);
    rep(i,0,n) cin>>v[i];
    sort(all(v));

    int ans = -2e9;
    rep(i,1,n-1){
        ans = max({ans, abs(v[i-1]+v[n-1]-2*v[i]), abs(v[0]+v[n-i]-2*v[n-i-1])});
    }
    cout<<ans<<'\n';


}