P171PROF - ROUND 1F - Học Bổng

Link Sub: http://www.spoj.com/PTIT/problems/P171PROF/
Người Gửi: Dương Lee

• Problem:

Sau một học kì học tập vất vả. Giờ Cường đang đi nhận học bổng, nhưng mà có rất nhiều người đang đợi như cường và họ phải xếp hàng. Cường muốn cải thiện thời gian chờ đợi để nhanh được ra tiệm net.  
Có n người đang đợi để nhận học bổng. với mọi người chúng ta đều biết trước thời gian mà người đó cần để hoàn thành thủ tục. Một người sẽ thất vọng khi thời gian người đó chờ đợi nhiều hơn thời gian mà họ làm thủ tục. Thời gian một người chờ đợi là tổng thời gian khi tất cả những người đứng trong hàng đợi trước mặt mình được làm thủ tục. Cường nghĩ rằng nếu trao đổi một số người thì có thể giảm số người thất vọng.  
Bạn hãy giúp cường tìm ra số lượng người tối đa không phải thất vọng khi đợi học bổng.

Input

Dòng đầu tiên chứa số nguyên n ( 1 ≤  n  ≤ 105 ).

Dòng tiếp theo chứa n số nguyên ti ( 1 ≤  ti  ≤ 109 ), cách nhau bằng dấu cách.

Output

In một số duy nhất - số lượng tối đa của mọi người không thất vọng trong hàng đợi.

Example:

Input

5
15 2 1 5 3

Output:

4

• Solution:

- Tối ưu ban đầu: Sắp xếp cho dãy tăng dần code dưới đây dùng sort trong thư viện (heap sort).
- Sau khi đã có dãy tăng dần ta áp dụng phương án tối ưu sau: Tại mỗi phần tử (t[i]) ta tính tổng tất cả các số trước nó (S).
+ Nếu S<=t[i] thì người đó không bị thất vọng.
+ Nếu S>t[i] thì người đó sẽ thất vọng và ta sẽ gán t[i]=0. Vì sao lại = 0? Vì ta coi người đó bị thất vọng và coi như chuyển người đó về cuối dãy.
(Thực chất bài này là tìm dãy con có F[i]>=sum(F[i-j], j:=1->i) mà dài nhất. Nhưng vì n=10^5 nên ta có thể dùng tham lam giả QHĐ)

• Code:

C++:

https://ideone.com/cT1DZ3

#include <iostream>
#include <algorithm>
using namespace std;

main ()
{
    long n;
    cin>>n;
    long long t[n];
    for (int i=0; i<n; i++)
    {
        cin>>t[i];
    }
    
    sort (t, t+n);
    
    long dem=1;
    for (int i=1; i<n; i++)
    {
        long long s=0;
        for (int j=0; j<i; j++)
        {
            s=s+t[j];
        }
        if (s<=t[i])
        {
            dem++;
        }
        else
        {
            t[i]=0;
        }
    }
    cout<<dem;
} 

JAVA:

...

Python:

...

Author : DL

Share this

Related Posts