Submission #1370370

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

#define fr first
#define sc second
#define pb push_back
#define mpr make_pair
#define ppb pop_back()
#define ins insert
#define sz(s) int(s.size())
#define all(x) x.begin(), x.end()
#define lb lower_bound
#define ub upper_bound
const int N = 1e5 + 1;
ll p[N];
int a[N], n;
bool check(int x){
	ll sum = p[x];
	for(int i = x + 1;i <= n; ++ i){
		if(a[i] > sum * 2)return 0;
		sum += a[i];
	}
	return 1;
}
int main()
{
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n; ++ i){
		cin >> a[i];
	}
	sort(a + 1,a + n + 1);
	for(int i = 1;i <= n; ++ i){
		p[i] = p[i - 1] + a[i];
	}
	int l = 1,r = n;
	while(l < r){
		int mid = (l + r) / 2;
		if(check(mid))r = mid;
		else l = mid + 1;
	}
	cout << n - l + 1;
	return 0;
}

Submission Info

Judge Result