解題區/解題區 - UVa

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;
}