[Tmt514] Beverage Cup 2 F - No challenge No life

contents

  1. 1. Problem
  2. 2. Solution

Problem

這次要挑戰的題目為 UVa 12647 - Balloon,由於網路上有一些線段樹的作法,如

http://www.cnblogs.com/yours1103/p/3426212.html

這裡可以看到有一些人利用線段樹來完成操作,實際上的做法根據掃描線,y 座標從高度低到高、或者是高到低的線段依序放入,到時候查找第一個獲最後一個覆蓋的線段編號。

UVa 12647 - Balloon 主要是在問,給予一些天花板,請問放置一個氣球,氣球會沿著天花板歪斜的地方移動 (如果沒歪則停止),詢問最後停留的位置。有可能會飛到無窮遠,則輸出最後的 x 座標,反之輸出停留的 (x, y) 地點。如果發生一個地點有數個天花板,發生擦邊情況,則氣球會依據第一個碰觸到的天花板進行移動。

Solution

既然發現它們 (搜尋可以找到至少兩個大大的線段樹寫法) 基本上都是按照覆蓋的方式,找到覆蓋編號去完成移動、建造飛行的所有可能。

明顯地,由於天花板線段的斜率有正有負,不能保證根據 y 座標排序可以決定飛行到下一個的高度的 x 範圍。因此交錯 y 座標線段,讓覆蓋方案失效。

下面有數組測資,可以讓史蒂芙掉測資、也會讓網址中的代碼掉。史蒂芙認為覆蓋不好,那用最大最小值去維護如何!這樣也許就好點了吧?但不幸地,這麼做一樣會遇到排序 y 的問題,不管怎麼排序,都會造成建構方法不正確。

challenge 的題目還不太會傳,中間有點小問題。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <stdio.h> 

int main() {
// puts("4 1");
// puts("3 1 12 4");
// puts("5 2 2 3");
// puts("1 4 4 3");
// puts("7 5 14 5");
// puts("4");

puts("3 3");
puts("5 5 10 4");
puts("2 2 6 4");
puts("0 3 4 4");
puts("0");
puts("1");
puts("2");

// puts("7 4");
// puts("3 1 12 4");
// puts("5 2 2 3");
// puts("1 4 4 3");
// puts("7 5 14 5");
// puts("25 5 30 4");
// puts("22 2 26 4");
// puts("20 3 24 4");
// puts("4");
// puts("20");
// puts("21");
// puts("22");
return 0;
}

/*
3 3
5 5 10 4
2 2 6 4
0 3 4 4
0
1
2
4 1
3 1 12 4
5 2 2 3
1 4 4 4
7 5 14 5
4
4 1
3 1 12 4
5 2 2 3
1 4 4 3
7 5 14 5
4
*/