w22116972
3/18/2014 - 10:20 AM

10714-Ants

10714-Ants

//
//  main.cpp
//  10714
//
//  Created by Edward on 2014/3/8.
//  Copyright (c) 2014年 Edward. All rights reserved.
//

#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <stdio.h>

using namespace std;

int main(int argc, const char * argv[])
{
    int n;
    cin >> n;
    while (n--) {
        int len,ant;
        cin >> len >> ant;
        vector<int> loc;
        while (ant--) {
            int t;
            cin >> t;
            loc.push_back(t);
        }
        sort(loc.begin(), loc.end());
        
        vector<int> minTime,maxTime;
        
        // 這個設計的概念主要是到底螞蟻撞在一起後反向走會影響什麼?
        // 因此可以先以題目的第一個例子來看
        // 假設螞蟻在2,7 len=10
        // if 撞到沒差
        // then A : 2->10 = 8 ; B : 7->0 = 7
        // else 撞到反向
        // then A : 2->5->0 = 7 ; B : 7->4->10 = 8
        // 這題就像高中數學裡的平面的折射圖一樣 反射回來的線視為延伸出去來計算即可
        
        // 再來是要把每隻螞蟻的最快和最慢時間都記錄下來
        // 因此minTime , maxTime 分別記錄每次螞蟻的最快和最慢時間
        // 但因為要等所有螞蟻都走完 所以最後取時間的時候都要取最慢的 max_element
        
        // 而每隻螞蟻的時間可分為往前走跟往後走 也就是現在位置到起點 和 現在位置到終點 這兩個情形
        // 因此使用 ? : 來決定max , min
        
        for (int i=0; i<loc.size(); i++) {
            int max = len-loc[i]>=loc[i] ? len-loc[i] : loc[i];
            maxTime.push_back(max);
            int min = len-loc[i]>=loc[i] ? loc[i] : len-loc[i];
            minTime.push_back(min);
        }
        cout << *max_element(minTime.begin(), minTime.end())<<" "<< *max_element(maxTime.begin(), maxTime.end()) << endl;
        loc.clear();
        minTime.clear();
        maxTime.clear();
    }
   
    return 0;
}