poj 1852 Ants

男娘i 2022-10-13 12:50 109阅读 0赞

[http://poj.org/problem?id=1852][http_poj.org_problem_id_1852]

## 题目大意 ##

army 陆军，大军

reside 居住

一群蚂蚁走在长为 1 c m 1cm 1cm的水平杆上，每个的速度是 1 c m / s 1cm/s 1cm/s

当走到尽头，掉下去。

当两只碰到一起，那么两只往反方向走。

知道它们的初始位置，不知道原始蚂蚁的移动方向。

求蚁群全部掉下去的最早和最晚时间

--------------------

## 题解 ##

最小值：找到一个比较靠近中心的蚂蚁，让它往最近的终点掉落的时间

最大值：找到一个蚂蚁，它距离对面的终点最远，让它掉落的时间

先排序（数据是无序的）

--------------------

## 代码 ##

//#include <bits/stdc++.h>
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <vector>
    #define rep(i,l,r) for(int i=l;i<=r;i++)
    #define all(a) (a).begin(),(a).end()
    #define pb push_back
    using namespace std;
    typedef long long ll;
    typedef vector<int> vi;
    
    int n,p,tmp,a1,a2;
    
    int main() { 
        int t; cin >> t;
        while(t--){ 
            cin >> p >> n; 
            vi a;
            rep(i,1,n) cin >> tmp, a.pb(tmp);
            sort(all(a));
            rep(i,0,n-1){ 
                a1=max(a1,min(a[i],p-a[i]));
                a2=max(a2,max(a[i],p-a[i]));
            }
            //a2 = max(p-a[0],a[n-1]); 如果是这样的话，p=200，a[0]=190,a[n-1]=195,不成立
            cout << a1 << " " << a2 << endl;
        }
        return 0;
    }

--------------------

## 代码二 ##

#include<iostream>
    #include<cmath>
    using namespace std;
    
    int main()
    { 
        int n,l,t;
        cin >> t;
        while(t--)
        { 
            int min1 = 0,max1 = 0,x;
            cin >> l >> n;
            for(int i = 0;i < n;i++)
            { 
                cin >> x;
                if(x <= l / 2)
                { 
                    min1 = max(min1,x);
                    max1 = max(max1,l - x);
                }
                else
                { 
                    min1 = max(min1,l - x);
                    max1 = max(max1,x);
                }
            }
            cout << min1 << " " << max1 << endl;
        }
        return 0;
    }
    // https://www.cnblogs.com/biaobiao88/p/11832757.html

--------------------

[http_poj.org_problem_id_1852]: http://poj.org/problem?id=1852