Login with GitHub. Nope?
修正 C++ 的程式碼在使用一定量動態記憶體後會產生 RF 的問題 @ 2019/12/6 4:45pm NeoHOJ 強勢復活中 (Open beta)
Submit　　Ranklist

Problem : 86 - 接金幣

Special Judge

Problem Statistics

Solved Member: 11　　Submission: 46　　User Tried: 11

Statement:

你玩過大富翁的接金幣嗎?

現實世界中你是個接金幣的高手，你對於接金幣的細節瞭若指掌。
你發現，有 N 個金幣會在固定的時間掉落在水平座標的地圖上，你必須剛好在掉落的時刻或者提前到那個地點來等金幣掉下來。
由於地圖很大，專業的你還聘請了許多人來幫你一起接金幣。剛開始的時候(時間 = 0)每個人的位置可以任意排，且每個人在 1 的時間之內可以移動最長的距離為 1。你想知道，若要接到所有的金幣，最少需要多少人來接。

Input:Output:

第 1 行有一個數字 N ，代表有多少金幣要接。
後面有 N 行，每行有 Si, Ti兩個數字，代表有一個金幣會在 Ti 的時間掉在 Si 的地方。

1 ≤ N ≤ 100000
0 ≤ Si, Ti ≤ 1000000000

20%的測資滿足：N ≤ 85 且 最小雇用的人數 ≤ 4
60%的測資滿足：N ≤ 8000
請輸出任意一組合理的解答。

第 1 行輸出一個數字 k ，代表最少需要多少人才能夠接完所有金幣。
第 2 行開始的後 N 行每行請輸出 3 個數字 Si Ti Ji，代表 Ti 時間掉在 Si 地方的這一塊金幣會由第 Ji(1 ≤ Ji ≤ k) 個人來接。
糖果以及人的順序皆可以隨意排列。

Sample Input:Sample Output:

5
1 1
2 3
1 5
3 4
2 6
2
1 1 1
2 3 1
1 5 2
3 4 1
2 6 2

Source:

BOI 2009

Problem Setter

Testdata:

TestTimeMemoryScore
01500ms65536kb
1-11500ms65536kb5
1-21500ms65536kb
1-31500ms65536kb
1-41500ms65536kb
1-51500ms65536kb
2-11500ms65536kb5
2-21500ms65536kb
2-31500ms65536kb
2-41500ms65536kb
2-51500ms65536kb
2-61500ms65536kb
3-11500ms65536kb5
3-21500ms65536kb
3-31500ms65536kb
3-41500ms65536kb
3-51500ms65536kb
3-61500ms65536kb
4-11500ms65536kb5
4-21500ms65536kb
4-31500ms65536kb
4-41500ms65536kb
4-51500ms65536kb
4-61500ms65536kb
5-11500ms65536kb5
5-21500ms65536kb
5-31500ms65536kb
5-41500ms65536kb
5-51500ms65536kb
5-61500ms65536kb
6-11500ms65536kb5
6-21500ms65536kb
6-31500ms65536kb
6-41500ms65536kb
6-51500ms65536kb
6-61500ms65536kb
7-11500ms65536kb5
7-21500ms65536kb
7-31500ms65536kb
7-41500ms65536kb
7-51500ms65536kb
7-61500ms65536kb
8-11500ms65536kb5
8-21500ms65536kb
8-31500ms65536kb
8-41500ms65536kb
8-51500ms65536kb
8-61500ms65536kb
9-11500ms65536kb5
9-21500ms65536kb
9-31500ms65536kb
9-41500ms65536kb
9-51500ms65536kb
9-61500ms65536kb
10-11500ms65536kb5
10-21500ms65536kb
10-31500ms65536kb
10-41500ms65536kb
10-51500ms65536kb
10-61500ms65536kb
10-71500ms65536kb
11-11500ms65536kb5
11-21500ms65536kb
11-31500ms65536kb
11-41500ms65536kb
11-51500ms65536kb
11-61500ms65536kb
11-71500ms65536kb
12-11500ms65536kb5
12-21500ms65536kb
12-31500ms65536kb
12-41500ms65536kb
12-51500ms65536kb
12-61500ms65536kb
12-71500ms65536kb
13-11500ms65536kb5
13-21500ms65536kb
13-31500ms65536kb
13-41500ms65536kb
13-51500ms65536kb
13-61500ms65536kb
13-71500ms65536kb
14-11500ms65536kb5
14-21500ms65536kb
14-31500ms65536kb
14-41500ms65536kb
14-51500ms65536kb
14-61500ms65536kb
14-71500ms65536kb
14-81500ms65536kb
15-11500ms65536kb5
15-21500ms65536kb
15-31500ms65536kb
15-41500ms65536kb
15-51500ms65536kb
15-61500ms65536kb
15-71500ms65536kb
15-81500ms65536kb
16-11500ms65536kb5
16-21500ms65536kb
16-31500ms65536kb
16-41500ms65536kb
16-51500ms65536kb
16-61500ms65536kb
16-71500ms65536kb
16-81500ms65536kb
17-11500ms65536kb5
17-21500ms65536kb
17-31500ms65536kb
17-41500ms65536kb
17-51500ms65536kb
17-61500ms65536kb
17-71500ms65536kb
17-81500ms65536kb
18-11500ms65536kb5
18-21500ms65536kb
18-31500ms65536kb
18-41500ms65536kb
18-51500ms65536kb
18-61500ms65536kb
18-71500ms65536kb
18-81500ms65536kb
19-11500ms65536kb5
19-21500ms65536kb
19-31500ms65536kb
19-41500ms65536kb
19-51500ms65536kb
19-61500ms65536kb
19-71500ms65536kb
19-81500ms65536kb
20-11500ms65536kb5
20-21500ms65536kb
20-31500ms65536kb
20-41500ms65536kb
20-51500ms65536kb
20-61500ms65536kb
20-71500ms65536kb
20-81500ms65536kb

NeoHOJ — The new era of HOJ
頁面讀取時間: 0.0068 秒，使用記憶體: 0.85MB 。
GitHub