uva 10714 - Ants

点击打开链接uva10714

题目意思：    有一群蚂蚁在走动，走的速度都是1cm/s，现在有一段长度为L的路，只知道蚂蚁的位置但是不知道蚂蚁的走的方向，每个蚂蚁走的不一定是相同的，现在有如果有两只蚂蚁从相反方向走的时候碰头了，那么所有的蚂蚁马上走向相反的方向，问我们当所有蚂蚁都走到终点（两边都是终点）时候最小的时间和最大的时间

解题思路：       1：先看一个小例子：0—————A（4）—》——《—B（8）—————10，在图上有两只蚂蚁同时出发，现在A蚂蚁从左往右走1 cm/s，B蚂蚁从右往左也是 1 cm/s，如果A  B相遇的时候就和A走相同的方向，问A B到达终点时候B走了多远，由图知道A  B是同时走的，并且A  B速度一样，那么我们知道A B最终肯定是一起到的终点，所以B 走的路程就是A 走的路程，所以B走的路程就是10-4 = 6
                         2：现在来看这一题，其实和上面是一样的原理，只是蚂蚁多来而已。那么现在来分析一下，假设路径为A——————D—C（中心）—E————————B，图上A B分别为两端的终点，由图可知：C到达A  B的路程都是相同的；D点到达A的路程小于到达B；E点到达B的路程小于到达A；由上面图，那么知道我们要从中心出发去考虑最小值个最大值
                       3：样列解析
                       1只有一个点：  
                       1：10  2           0——2————————10                             最小值是2，最大值是8  
                       2：10  6           0———————6———10                             最小值是4，最大值是6
                       2 所有点在中心的左边
                       10 4
                       1 2 3 4              0—1—2—3—4——————————10        最小值是4，最大值是9
                       3 所有点在中心的右边
                       10 4
                       6 7 8 9              0—————————6—7—8—9——10        最小值是4，最大值是9
                       4 中心两边都有
                       10 4
                       2 4 6 8              0——2——3————6————9——10         最小值是4，最大值是9   

代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <set>
using namespace std;
#define MAXN 100010

int t , l , n;
int pos[MAXN];

void solve() {
    int pos_r , pos_l;
    int min , max;
    sort(pos , pos+n);
    //只有左半部分
    if(pos[0] >= l/2){
        printf("%d %d\n" , l-pos[0] , pos[n-1]);
        return;
    }
    //只有右半部分
    if(pos[n-1] < l/2){
        printf("%d %d\n" , pos[n-1] , l-pos[0]);
        return;
    }
    //两边都有
    for(int i = 0 ; i < l ; i++){
        if(pos[i] < l/2 && pos[i+1] >= l/2){
            pos_l = i ; pos_r = i+1;//找到中心旁边的两个点
            break;
        }
    }
    //求出最大值和最小
    min = pos[pos_l]>l-pos[pos_r]?pos[pos_l]:l-pos[pos_r];
    max = l-pos[0]>pos[n-1]?l-pos[0]:pos[n-1];
    printf("%d %d\n" , min , max);
    
}

int main() {
   // freopen("input.txt" , "r" , stdin);
    scanf("%d" , &t);
    while(t--){
        scanf("%d%d" , &l , &n);
        for(int i = 0 ; i < n ; i++)
            scanf("%d" , &pos[i]);
        if(n != 1) solve();
       //一个点的时候特判
        else{
            if(pos[0] > l/2) printf("%d %d\n" , l-pos[0] , pos[0]);
            else printf("%d %d\n" , pos[0] , l-pos[0]);
        }
    }
    return 0;
}