4307_개미.cpp

#include <iostream>
#include <vector>
using namespace std;

int T; // 테스트 횟수
int L; // 막대 사이즈
int N; // 개미수

vector<int> positions; // 입력값들이 저장됨
vector<int> earlies;   // 최소시간들이 저장됨
vector<int> lates;     // 최대시간들이 저장됨
bool pos[1000001];     // 개미의 위치를 표시하는데 사용됨

int main(){
    cin>>T;
    for(int t=0; t<T; t++){
        cin>>L>>N;
        for(int i=1; i<=N; i++){
            int temp;
            cin>>temp;
            pos[temp] = true;
            positions.push_back(temp);
        }
        
        /* 최소 구하기 */
        int l_index = L/2;
        int r_index = L/2;
        if(L%2==1){
            r_index = L/2+1;
        }
        // 좌우 인덱스를 하나씩 감소/증가 시켜서
        // 중앙으로부터 가장 가까운 개미의 위치를 파악한다.
        while(true){
            if(pos[l_index]){
                // 왼쪽 인덱스라면 막대의 끝(0)과 가까움
                earlies.push_back(l_index);
                break;
            }
            else if(pos[r_index]){
                // 오른쪽 인덱스라면 막대의 끝(L)과 가까움
                earlies.push_back(L-r_index);
                break;
            }
            else{
                l_index-=1;
                r_index+=1;
            }
        }
        
        /* 최대 구하기 */
        // 개미가 0 또는 L인 경우도 고려해줘야한다.
        l_index=0;
        r_index=L;
        while(true){
            if(pos[l_index]){
                // 왼쪽 인덱스라면 막대의 끝(L)과 더 멀리 떨어져 있음
                lates.push_back(L-l_index);
                break;
            }
            else if(pos[r_index]){
                // 오른쪽 인덱스라면 막대의 끝(0)과 더 멀리 떨어져 있음
                lates.push_back(r_index);
                break;
            }
            else{
                l_index+=1;
                r_index-=1;
            }
        }
        
        /* 입력값 관련 초기화 */
        for(int i=0; i<=L; i++){
            pos[i]=false;
        }
        positions.clear();
    }
    
    /* 출력 */
    for(int t=0; t<T; t++){
        cout<<earlies[t]<<" "<<lates[t]<<endl;
    }
    return 0;
}