排水系统

排水系统

时间： 1ms        内存：128M

描述：

有n个出水口，第i个出水口的出水量为si，在入水口加入A的水量，问你至少堵掉多少出水口才能使第一个水管出水量至少为B。出水量计算公式(s1*A)/S，S表示未堵掉出水口出水量之和。

输入：

第一行包含三个数  n A B  含义题目中已给出  (1<=n<=100000, 1<=B<=A<=10000)
第二行为n个数字 s1,s2,s3...sn (1<=si<=10000) 代表出水口大小

输出：

至少堵住多少出水口，可以使得第一个水管出水量至少为B。

示例输入：

4 10 3
2 2 2 2

示例输出：

1

提示：

参考答案（内存最优[1508]）：

#include<cstdio>
#include<algorithm>
using namespace std;
int n,a,b,s[100005],sum;
int main()
{
	int i;
	scanf("%d%d%d",&n,&a,&b);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&s[i]);
		sum+=s[i];
	}
	if(n<=1)
	{
		printf("0\n");
		return 0;
	}
	sort(s+2,s+n+1);
	if(s[1]*a/sum>=b)
	{
		printf("0\n");
		return 0;
	}
	int y=0;
	for(i=n;i>1;i--)
	{
		sum-=s[i];
		y++;
		if(s[1]*a/sum>=b)
		{
			break;
		}
	}
	printf("%d\n",y);
	return 0;
} 

参考答案（时间最优[7]）：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
int s[maxn];
int main() 
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    int n,A,B;
    cin>>n>>A>>B;
    int sum=0;
    rep(i,1,n) {
    	cin>>s[i];
    	sum+=s[i];
    }
    sort(s+2,s+n+1);
    int nape=0,t=n;
    int i;
    for(i=1;i<n;i++)
    {
    	nape+=s[t];
    	t--;
    	if((s[1]*A)/(sum-nape)>=B)
    		break;
    }
    if((s[1]*A)/sum>=B)
    	i=0;
    cout<<i<<endl;
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。