UVa 11670 - Physics Experiment

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

物理加熱實驗,每個粒子在一個長棒上,加熱長棒的一端,粒子水平左右移動速度為 1,當距離加熱粒子小於等於 D 時,加熱狀態就會被傳遞。

給定每一個粒子的位置,現在從座標 0 的位置進行加熱,請問所有粒子都呈現加熱狀態需要幾秒。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
5
0.000
3.000
4.500
7.000
10.000
2.500
2
0.000
6.000
3.000
0

Sample Output

1
2
Case 1: 0.250
Case 2: 1.500

Solution

貪心盡可能讓粒子往原點移動,維護一個當前使用時間 t,前 i 個粒子的傳遞時間最短下,最右側的粒子能距離原點最遠為何。

加入下一個粒子時 (不考慮在 t 秒內的移動),若距離大於 D,且藉由 t 時間內的移動仍然無法接近到加熱粒子 D 以內,則表示需要額外時間來接近加熱粒子 (加熱粒子與未加熱粒子彼此靠近)。反之,則在 t 秒內慢慢移動到加熱粒子恰好能傳遞的距離上 (類似接力賽跑的接棒過程)。如果下一個粒子距離小於 D,表示在 t 秒內可以進可能遠離到恰好接棒的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
#include <algorithm>
using namespace std;
// greedy, math
const int MAXN = 100005;
double pos[MAXN], D;
int main() {
int n, cases = 0;
while (scanf("%d", &n) == 1 && n) {
for (int i = 0; i < n; i++)
scanf("%lf", &pos[i]);
scanf("%lf", &D);

sort(pos, pos + n);
double t = 0;
for (int i = 1; i < n; i++) {
if (pos[i] - pos[i-1] > D) { // at t-time, i-th object must move left
if ((pos[i] - t) - pos[i-1] > D) { // late
double move = ((pos[i] - t) - pos[i-1] - D)/2;
pos[i] = pos[i] - move - t; // move: move left to be heated, t: greedy move left, at t-time.
t += move;
} else {
pos[i] = pos[i-1] + D;
}
} else { // i-th object move right
if (pos[i] + t < pos[i-1] + D)
pos[i] = pos[i] + t;
else
pos[i] = pos[i-1] + D;
}
}
printf("Case %d: %.3lf\n", ++cases, t);
}
return 0;
}