Problem Description

?通過懸崖的yifenfei，又面臨著幽谷的考驗—— 幽谷周圍瘴氣彌漫，靜的可怕，隱約可見地上堆滿了骷髏。由于此處長年不見天日，導致空氣中布滿了毒素，一旦吸入體內(nèi)，便會全身潰爛而死。 幸好yifenfei早有防備，提前備好了解藥材料（各種濃度的萬能藥水）?，F(xiàn)在只需按照配置成不同比例的濃度。 現(xiàn)已知yifenfei隨身攜帶有n種濃度的萬能藥水，體積V都相同，濃度則分別為Pi%。并且知道，針對當時幽谷的瘴氣情況，只需選擇部分或者全部的萬能藥水，然后配置出濃度不大于 W%的藥水即可解毒。 現(xiàn)在的問題是：如何配置此藥，能得到最大體積的當前可用的解藥呢？ 特別說明：由于幽谷內(nèi)設備的限制,只允許把一種已有的藥全部混入另一種之中（即：不能出現(xiàn)對一種藥只取它的一部分這樣的操作）。

提示：多種藥水混合后的濃度=(濃度1*體積1+濃度2*體積2+……)/(體積和)

?

Input

?輸入數(shù)據(jù)的第一行是一個整數(shù)C，表示測試數(shù)據(jù)的組數(shù)； 每組測試數(shù)據(jù)包含2行，首先一行給出三個正整數(shù)n,V,W(1<=n,V,W<=100)； 接著一行是n個整數(shù)，表示n種藥水的濃度Pi%(1<=Pi<=100)。

Output

?對于每組測試數(shù)據(jù)，請輸出一個整數(shù)和一個浮點數(shù)； 其中整數(shù)表示解藥的最大體積，浮點數(shù)表示解藥的濃度(四舍五入保留2位小數(shù))； 如果不能配出滿足要求的的解藥，則請輸出0 0.00。

Example Input

3 1 100 10 100 2 100 24 20 30 3 100 24 20 20 30

Example Output

0 0.00 100 0.20 300 0.23 #include<stdio.h> int a[120]; void qsort(int l,int r)//快排； { ?int i=l,j=r,key=a[l];if(i>=j) ? ? ? ?return ;while(i<j){ ? while(i<j&&key<=a[j]) ?j--;a[i]=a[j];while(i<j&&key>=a[i]) ? i++;a[j]=a[i];}a[i]=key; ? ?qsort(l,i-1); ? ?qsort(i+1,r); } int main() { ? int t,n,v,w,i,j,k,m;double s,sum;scanf("%d",&t);for(k=1;k<=t;k++){ ? scanf("%d%d%d",&n,&v,&w);for(i=0;i<n;i++)scanf("%d",&a[i]);qsort(0,n-1);if(a[0]>w){ ?printf("0 0.00\n");continue;}else {sum=a[0];m=1;for(i=1;i<n;i++){s=sum+a[i];if(s/(i+1)<=w)//能配成功；{sum=s; ?m=m+1;continue;}else ? ?break;}s=sum*v/(m*v);v=m*v;printf("%d %.2lf\n",v,s/100);}}return 0; ?}

總結

以上是生活随笔為你收集整理的迷瘴的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。