백준: 20175

</br> 2020 본선 중 골드 문제 풀기
</br>

20175: Mobile Robot

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

1~n까지의 로봇들이 수직선 위에 어딘가 있다
그런데 (i, i+1) 사이가 정확히 d씩 떨어지게 정렬할 때, 최대로 움직여야 하는 로봇이 이동한 거리가 최소가 되게 하면 그 때의 이동 거리는 얼마일까

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll robots[1000001];
ll n, d;

pair<ll, bool> func(bool rev){
    ll nowd = LLONG_MAX;
    ll start = 0;
    ll l = -10000000000000000;
    ll r = 10000000000000000;
    while( l <= r ){
        ll t = 0;
        ll m = 0, p = 0;
        ll mid = (l+r) / 2;
        if( rev ){
            for(int i = n-1; i >= 0; i--){
                ll c = mid - robots[i] + d*(n-1-i);
                t = max(t, abs(c));
                if( c < 0 ) m = min(m, c);
                else p = max(p, c);
            }
        }
        else{
            for(int i = 0; i < n; i++){
                ll c = mid - robots[i] + d*i;
                t = max(t, abs(c));
                if( c < 0 ) m = min(m, c);
                else p = max(p, c);
            }
        }
        if( t < nowd ){
            nowd = t;
            start = mid;
        }

        if( m+p < 0 ) l = mid+1;
        else r = mid-1;
    }

    ll m = 0, p = 0;
    if( rev ){
        for(int i = n-1; i >= 0; i--){
            ll c = start - robots[i] + d*(n-1-i);
            if( c < 0 ) m = min(m, c);
            else p = max(p, c);
        }
    }
    else{
        for(int i = 0; i < n; i++){
            ll c = start - robots[i] + d*i;
            if( c < 0 ) m = min(m, c);
            else p = max(p, c);
        }
    }

    if( m+p == 1 ) return make_pair(abs(p)-1, true);
    else if( m+p == -1 ) return make_pair(abs(m)-1, true);
    else if( m+p == 0 ) return make_pair(nowd, false);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed;

    cin >> n >> d;

    for(int i = 0; i < n; i++){
        cin >> robots[i];
    }

    pair<ll, bool> ret1 = func(false);
    pair<ll, bool> ret2 = func(true);
    if( ret1.first == ret2.first ){
        if( !ret1.second || !ret2.second ) cout << ret1.first << ".0\n";
        else cout << ret1.first << ".5\n";
    }
    else if( ret1.first < ret2.first ){
        if( ret1.second ) cout << ret1.first << ".5\n";
        else cout << ret1.first << ".0\n";
    }
    else{
        if( ret2.second ) cout << ret2.first << ".5\n";
        else cout << ret2.first << ".0\n";
    }

}

일단 다 long long으로 입력 받고 연산해야 한다
로봇이 (start, start+d, start+2*d, ..., start+(n-1)*d)의 형태로 늘어서게 될 것이다.
하나 하나 다 할 수 없으므로, 이분탐색으로 시작점을 잡고 최소가 되는 지점을 구하자
l과 r의 업데이트는 마이너스 차이의 최대와 플러스의 차이의 최대를 구해서, 만약 마이너스 쪽 절대값이 더 크면 시작점이 너무 왼쪽이 있으므로 l을 업데이트 하는 식으로 했다.

그런데 3번 예제를 보면, 소수점 단위로 나오기도 한다.
아마 마이너스 차의 최대와 플러스 차의 최대는 0 또는 1일 것이라 가정하고, .5까지만 따로 처리해 주도록 했다
혹시 double 연산에 문제 있을까 봐 정수로 계산하고 문자열로 출력함

ex) 예제 3
5 1
1 3 5 9 7

이분탐색으로 3 4 5 6 7을 찾았다.
 3  4  5  6  7
 2  1  0 -3  0
거리 구하면 이럼

마이너스 차의 최대는 -3고, 플러스 차의 최대는 2이다.  
따라서 .5 단위의 중간점에서 시작해야 한다.  

 2.5  3.5  4.5  5.5  6.5
 1.5  0.5 -0.5 -3.5 -0.5
-0.5 하면 이렇게

 3.5  4.5  5.5  6.5  7.5
 2.5  1.5 0.5 -2.5 0.5
+0.5 하면 이렇게

따라서 각 최대가 -2.5와 2.5가 되므로, 답은 2.5

</br>

그런데 계속 2%에서 틀린다 뭐지
혹시 몰라서 cout << fixed도 했는데

대체 뭘까 했는데 로봇들이 (start+(n-1)*d, start+(n-2)*d, ..., start)의 형태로 있을 수도 있다!!! 앞 번호가 더 뒤에 있을 수도 있었음
인덱스를 거꾸로 탐색도 한 번 해 줘서, 둘 중 더 작은 애로 출력해 주면 된다.
</br>

---

문제가 정확히 이해가 안 돼서 자꾸 번역 돌리는데 큰 일이다
</br>