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

Problem : 94 - Ricehub

Problem Statistics

Solved Member: 20　　Submission: 63　　User Tried: 20

Statement:

在鄉村你可以看到一條筆直的道路叫做稻米路，沿著這條路共有R 塊稻田，每塊稻田的座標為介於1 和L 的整數。這些稻田依照座標以非遞減的順序表示，正式來說，稻田i (0 ≤ i < R)的座標為X[i]，你可以假設1 ≤ X[0] ≤ ... ≤ X[R-1] ≤ L。

注意：不同塊的稻田可能有相同的座標。

我們計劃蓋一個稻米倉庫(rice hub)，用以儲存越多稻米越好。如同稻田座標，這個稻米倉庫的座標必須是介於1 和 L 的整數，它可以坐落在任何位置，包括稻田的位置。

每塊稻田在收割季節都正好生產一卡車的稻米，為了運送到稻米倉庫，這個城市必須雇用一位卡車司機。當司機運送一卡車的稻米至倉庫時，每單位距離收費一泰銖，換句話說，從一塊稻田運送稻米至倉庫的費用等同於它們座標的差值。

由於本收割季節的預算很緊，我們最多只能花B 泰銖的運送費用。你的任務是幫我們規劃出能收集越多稻米越好的倉庫位置。

Task:

找出一個最佳的倉庫座標，並回傳預算內所能運送至該倉庫的最大稻米量(以一卡車為單位)。

注意：運送稻米的總費用可能非常大。給定的預算為一個64 位元整數，因此我們建議你使用64 位元整數運算；你可使用C/C++的long long 資料型態或Pascal 的Int64 資料型態。

Input:Output:

第1行有3個整數，R,L,B，分別代表稻田數量、最大座標值、以及預算。
接下來R行，每一行各有一個數字X[i]，依序從最小值排至最大值，X[i]為稻田i 的座標，0 ≤ i < R。
輸出一個數字，在預算的限制下，最多可以收到幾卡車的米。

Sample Input:Sample Output:

5 20 6
1
2
10
12
14
3

HINT:

GRADING:
子題 1 (17 分)
●1 ≤ R ≤ 100
●1 ≤ L ≤ 100
●0 ≤ B ≤ 10 000
●所有稻田的座標皆不同(此情況僅限於本子題)。

子題2 (25 分)
●1 ≤ R ≤ 500
●1 ≤ L ≤ 10 000
●0 ≤ B ≤ 1 000 000

子題3 (26 分)
●1 ≤ R ≤ 5 000
●1 ≤ L ≤ 1 000 000
●0 ≤ B ≤ 2 000 000 000

子題4 (32 分)
●1 ≤ R ≤ 100 000
●1 ≤ L ≤ 1 000 000 000
●0 ≤ B ≤ 2 000 000 000 000 000

SAMPLE 解釋：

本範例有多個最佳的倉庫位置：你可以將它置於10 與14 之間的任一位置。
上圖顯示其中一個最佳倉庫位置。之後你可以從座標為10、12 以及14 的稻田運送稻米。對任一最佳倉庫位置而言，運送的總費用最多是6 泰銖。
此例中，沒有任何一個倉庫位置可以讓我們收集多於三塊稻田的稻米，因此這個答案是最佳解，所以回傳3。

Source:

IOI 2011

Problem Setter

Testdata:

TestTimeMemoryScore
01000ms262144kb
1-11000ms262144kb17
1-21000ms262144kb
1-31000ms262144kb
1-41000ms262144kb
1-51000ms262144kb
2-11000ms262144kb25
2-21000ms262144kb
2-31000ms262144kb
2-41000ms262144kb
2-51000ms262144kb
2-61000ms262144kb
2-71000ms262144kb
2-81000ms262144kb
2-91000ms262144kb
2-101000ms262144kb
2-111000ms262144kb
2-121000ms262144kb
2-131000ms262144kb
2-141000ms262144kb
2-151000ms262144kb
2-161000ms262144kb
2-171000ms262144kb
2-181000ms262144kb
2-191000ms262144kb
2-201000ms262144kb
2-211000ms262144kb
2-221000ms262144kb
2-231000ms262144kb
2-241000ms262144kb
2-251000ms262144kb
2-261000ms262144kb
3-11000ms262144kb26
3-21000ms262144kb
3-31000ms262144kb
3-41000ms262144kb
3-51000ms262144kb
3-61000ms262144kb
3-71000ms262144kb
3-81000ms262144kb
3-91000ms262144kb
3-101000ms262144kb
3-111000ms262144kb
3-121000ms262144kb
3-131000ms262144kb
3-141000ms262144kb
3-151000ms262144kb
3-161000ms262144kb
3-171000ms262144kb
3-181000ms262144kb
3-191000ms262144kb
3-201000ms262144kb
3-211000ms262144kb
3-221000ms262144kb
3-231000ms262144kb
3-241000ms262144kb
3-251000ms262144kb
3-261000ms262144kb
4-11000ms262144kb32
4-21000ms262144kb
4-31000ms262144kb
4-41000ms262144kb
4-51000ms262144kb
4-61000ms262144kb
4-71000ms262144kb
4-81000ms262144kb
4-91000ms262144kb
4-101000ms262144kb
4-111000ms262144kb
4-121000ms262144kb
4-131000ms262144kb
4-141000ms262144kb
4-151000ms262144kb
4-161000ms262144kb
4-171000ms262144kb
4-181000ms262144kb
4-191000ms262144kb
4-201000ms262144kb
4-211000ms262144kb
4-221000ms262144kb
4-231000ms262144kb
4-241000ms262144kb

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