Problem : 85 - 毛毛蟲問題

Problem Statistics

Solved Member: 28　　Submission: 186　　User Tried: 32

Statement:

你家有一個觀察箱，你想在裡面養很多很多的毛毛蟲。

你知道，每條毛毛蟲皆會行呼吸作用，排放出二氧化碳。一個觀察箱裡面如果二氧化碳的濃度太高，毛毛蟲就會死掉。具體一點來說，你有N隻毛毛蟲，分別用 1, 2, 3, ... ,N 來標號。毛毛蟲 i 會放出 $a_i$ 毫克的二氧化碳，並且最多可以吸收 $b_i$ 毫克的二氧化碳，如果吸收的二氧化碳超過這個量值就會死掉。

你發現在一個觀察箱當中，若放了編號 $i_1, i_2, ... , i_k$ 的 k 隻毛毛蟲，那麼每一隻毛毛重會平均吸收到$\LARGE \frac{a_{i_1} + a_{i_2} + ... + a_{i_k}}{k}$ 毫克的二氧化碳。你想計算看看一個觀察箱裡面最多可以放幾隻毛毛蟲。

Task:

給出 N 隻毛毛蟲可以接受的二氧化碳量以及排放的多寡，請你計算出最多有幾隻毛毛蟲可以同時在觀察箱裡面。

Input:Output:

第1行有1個正整數 N ，代表毛毛蟲的數量。
接下來的 N 行每行有2個正整數，$a_i , b_i$，分別代表毛毛蟲呼出的二氧化碳以及對二氧化碳的接受度(毫克)。

請你輸出一個整數，代表最多可以養幾隻毛毛蟲。

Sample Input:Sample Output:

6
12 8
5 9
2 4
10 12
6 7
13 9

HINT:

1 ≤ N ≤ 300000 = 3 × 10^5，N為毛毛蟲的數量
1 ≤ ai ≤ 100000 = 10^5，第i隻毛毛蟲排出的二氧化碳量(毫克)
1 ≤ bi ≤ 100000 = 10^5，第i隻毛毛蟲對二氧化碳的容許量(毫克)

30%測資滿足: N ≤ 1000

範例測資當中，選擇編號2, 4, 5三隻毛毛蟲，放出的二氧化碳量為 5 + 10 + 6 =21 毫克。
每一隻毛毛蟲會吸收到 $\large \frac{21}{3} = 7$ 毫克的二氧化碳，三隻的容許量為 9, 12, 7 毫克，皆不會死掉。並且，不存在4隻毛毛蟲可以同時存活在觀察箱的一種組合。

Source:

JOI 2010/2011 本選

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	3000ms	262144kb
1-1	3000ms	262144kb	10
1-2	3000ms	262144kb
1-3	3000ms	262144kb
1-4	3000ms	262144kb
1-5	3000ms	262144kb
2-1	3000ms	262144kb	10
2-2	3000ms	262144kb
2-3	3000ms	262144kb
2-4	3000ms	262144kb
2-5	3000ms	262144kb
2-6	3000ms	262144kb
2-7	3000ms	262144kb
3-1	3000ms	262144kb	10
3-2	3000ms	262144kb
3-3	3000ms	262144kb
3-4	3000ms	262144kb
3-5	3000ms	262144kb
3-6	3000ms	262144kb
3-7	3000ms	262144kb
3-8	3000ms	262144kb
4-1	3000ms	262144kb	10
4-2	3000ms	262144kb
4-3	3000ms	262144kb
4-4	3000ms	262144kb
4-5	3000ms	262144kb
4-6	3000ms	262144kb
5-1	3000ms	262144kb	10
5-2	3000ms	262144kb
5-3	3000ms	262144kb
5-4	3000ms	262144kb
5-5	3000ms	262144kb
5-6	3000ms	262144kb
6-1	3000ms	262144kb	10
6-2	3000ms	262144kb
6-3	3000ms	262144kb
6-4	3000ms	262144kb
6-5	3000ms	262144kb
6-6	3000ms	262144kb
7-1	3000ms	262144kb	10
7-2	3000ms	262144kb
7-3	3000ms	262144kb
7-4	3000ms	262144kb
7-5	3000ms	262144kb
8-1	3000ms	262144kb	10
8-2	3000ms	262144kb
8-3	3000ms	262144kb
8-4	3000ms	262144kb
9-1	3000ms	262144kb	10
9-2	3000ms	262144kb
9-3	3000ms	262144kb
9-4	3000ms	262144kb
9-5	3000ms	262144kb
10-1	3000ms	262144kb	10
10-2	3000ms	262144kb
10-3	3000ms	262144kb
10-4	3000ms	262144kb
10-5	3000ms	262144kb