[c++] 백준 #3163 떨어지는 개미 (190915)

< 풀이 >

약간의 관찰이 필요한 문제이다. 개미가 서로 부딫히면 방향을 바꾼다고 해서 겁먹고 시뮬레이션처럼 구하면 시간초과이다. (물론 난 그러지 않았다.) 개미가 서로 부딫히면 방향을 바꾼다는 의미는 부딫힌 개미와 떨어지는 데 걸리는 시간이 swap된다는 것이다. 그래서 이렇게 swap이 반복되고 나면(약간의 손계산으로 직접 해보면 알 수 있다) 최종적으로, 각 개미의 방향은 ← ← ← ← → → → 이런식으로 되서 다리 밖으로 떨어질 것이다. swap되는 시간도 고려해보면 최종적으로 각 개미가 떨어지는 데 걸리는 시간은 정렬된 배열의 무언가와 닮아 있는데,

-2 -3 -4 -5 7 3 2 1 이런 식으로 음수의 거리 값은 오름차순, 양수의 거리 값은 내림차순으로 정렬한 꼴로 정렬이 된다.

 

이제 각 개미가 언제 떨어질 지 아니까 그걸 바탕으로 양끝에서 개미를 victim으로 하나씩 떨궈보면 k번째 개미가 누군지 알 수 있다.

 

< 소스코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

#define pb push_back
#define N_MAX 100010


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T; cin >> T;
    while(T--){
        int N, L, k;
        cin >> N >> L >> k;
        vector<int> id(N, 0);
        vector<int> dist;
        vector<int> minus_dist;
        vector<ii> order(N, {0, 0});
        for(int i=0; i<N;i++){
            int p, a;
            cin >> p >> a;
            if (a > 0) dist.pb(L-p);
            else minus_dist.pb(p);
            id[i] = a;
        }
        sort(minus_dist.begin(), minus_dist.end());
        sort(dist.rbegin(), dist.rend());
        
        int t = 0;
        for(int i=0; i<minus_dist.size();i++){
            order[t].first = minus_dist[i];
            t++;
        }
        for(int i=0; i<dist.size();i++){
            order[t].first = dist[i];
            t++;
        }
        for(int i=0; i<N;i++){
            order[i].second = id[i];
        }
        int temp = 0;
        int begin = 0;
        int end = N-1;
        int victim = -1;
        while(temp<k){
            if (order[begin].first == order[end].first){
                if (order[begin].second < order[end].second){
                    victim = begin;
                    begin++;
                }
                else {
                    victim = end;
                    end--;
                }
            }
            else if (order[begin].first < order[end].first){
                victim = begin;
                begin++;
            }
            else{
                victim = end;
                end--;
            }
            temp++;
        }
        cout << order[victim].second << '\n';
    }


    return 0;
}