题目描述
有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
参考代码
#include<stdio.h>
int main()
{
int A,B,n,s[1000000],sum=0,i,j,num=0,m;
scanf("%d %d %d",&n,&A,&B);
for (i=0;i<n;i++)
{
scanf("%d",&s[i]);
sum+=s[i];
}
for (i=n-2;i>0;i--)
for (j=i+1,m=i;j<n;j++,i++)
{
if(s[i]>s[j])
{
s[i]=s[i]^s[j];
s[j]=s[i]^s[j];
s[i]=s[i]^s[j];
} else
{
i=m;
break;
}
}
i=n-1;
while((s[0]*A)/sum<B)
{
sum-=s[i--];
if(n==1)
break;
num++;
}
printf("%d",num);
return 0;
}
解析
暂无