Ants (PKU No.1852)
Ants (PKU No. 1852)
長さLcmの竿の上をn匹のありが毎秒1cmのスピードで歩いている。アリが竿の端に到達すると竿の下に落ちていく。また、竿の上は狭くてすれ違えないので、2匹のアリが出会うと、それぞれ反対を向いて戻っていく。各アリについて、現在の竿の左端からの距離は分かるが、どちらの方向を向いているかは分からない。全てのアリが傘から落ちるまでにかかる最小の時間と最大の時間をそれぞれ求める。
制約
アルゴリズム
ナイーブに全ての組み合わせ(各アリについて、初期の向き(左or右))を考えるととなり、現実的ではない。アリの速さが全部同じなのがポイントで、アリを区別しなければ、アリ同士が出会ったとき、素通りしていると考えても良い。なので、まず、各アリについて、両端までの時間(距離)を求める()。そして、最終的に求める時間は、
コード
import java.util.*; public class pku1852 { static Scanner scanner; public static void main(String[] args) { scanner = new Scanner(System.in); new pku1852(); } pku1852(){ int c; int L,n; c = scanner.nextInt(); while( c > 0 ){ c--; L = scanner.nextInt(); n = scanner.nextInt(); int[] x = new int[n]; for(int i = 0; i < n; i++) x[i] = scanner.nextInt(); solve(L, n, x); } } void solve(int L, int n, int[] x){ int MAX,MIN; MAX = MIN = 0; for(int i = 0; i < n; i++){ int A = Math.min(x[i], L - x[i]); int B = Math.max(x[i], L - x[i]); MIN = Math.max(MIN, A); MAX = Math.max(MAX, B); } System.out.println(MIN + " " + MAX); } }