UVA10714 Ants

· · 题解

题目传送门

双倍经验P1007

先给大家翻译一下题目：

有很多蚂蚁在一根棍子上，给定他们的初始位置，它们会朝着某个方向走 ( 速度 1 ) 。碰到另一只蚂蚁两只蚂蚁无法绕行，它们就都调头。请你安排它们初始的朝向来给出所有蚂蚁都到达棍子的两头 ( 即到达 0 或 l ) 的最短时间和最长时间。

同时这道题还有多组数据。

首先我们要知道 所有蚂蚁是等价的

所以在两只蚂蚁相遇时互相调头时和互相穿过对方是等价的

那么如果把互相调头都改成互相穿过对方 结果不变

所以问题就变成了：

很多蚂蚁给定初始位置 它们会向你指定的方向走直到走到 0 或 l ， 请给出所有蚂蚁都走到 0 或 l 的最短时间和最长时间

那这些蚂蚁互相都没有影响了

求最短时间就一只一只求最短时间然后再把所有最短时间取最后即可

求最短时间就一只一只求最长时间然后再把所有最长时间取最后即可

不必细说 直接上代码：

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int main(){
    int T;
    cin >> T;
    while(T--){
        int l,n;
        cin >> l >> n;
        int minans=-2e9,maxans=-2e9;
        for(int i=1;i<=n;i++)
            cin >> a[i];
        for(int i=1;i<=n;i++){
            minans=max(minans,min(a[i],l-a[i]));
            maxans=max(maxans,max(a[i],l-a[i]));
        }
        printf("%d %d\n",minans,maxans);
    }
    return 0;
}

顺带一提 P1007 就是本题去掉多组数据再稍加改动 有兴趣的同学们可以试试