POJ 1852 Ants(アナログ+弾性衝突)

原題アドレス
http://poj.org/problem?id=1852
标题:Lセンチの水平な木の棒にn匹のアリがいて、毎秒1 cm/sの速度で木の棒の端まで歩いて落ちる.開始位置(棒の左端点からの距離)がわかります.しかし、それらが這う方向は分かりません.2匹のアリが出会った後、振り向いて反対方向に行きます.すべてのアリが棒を落とす最短時間と最長時間を求めます.
問題を解く構想.
すべてのアリの初期向きを窮挙探索法で列挙すると,複雑度はO(2^n)であり,nが百万数級にある場合,運転時間は想像できない.アルゴリズムの最適化は次のとおりです.

最短時間については、明らかにすべてのアリが自分の最も近い端点に向かって前進すると、総時間が最も短いが、すべてのアリが落ちることを満たさなければならないので、すべてのアリから最も近い端までの距離の最大値をとる.

最長時間について,タイトルに記述されている2匹のアリが出会ってUターンするという行為は,本質的に時間に影響を及ぼさず,2匹のアリの違いを無視すればそれぞれがそのまま前進していると見なすことができる.そのため、アリを自分から最も遠い端点に向かわせ、すべてのアリから最も遠い端点までの距離の最大値を取ればよい.(実際には一番両側のアリを見るだけですが、ソートが複雑になります)

ACコード

#include 
#include 
using namespace std;

const int maxn = 1000005;
int pos[maxn];

int main()
{
    int kase, length, n;
    cin >> kase;
    while (kase--)
    {
        cin >> length >> n;
        for (int i = 0; icin >> pos[i];
        //      ，            
        int minT = 0;
        for (int i = 0; i//   max        
            minT = max( minT, min(pos[i], length-pos[i]) );

        //      ，             
        int maxT = 0;
        for (int i = 0; icout << minT << ' ' << maxT << endl;
    }
    return 0;
}

アルゴリズム複雑度:O(n)消費時間:610 ms(推定試験のnが大きい)