hdu 2570迷障水題

http://acm.hdu.edu.cn/showproblem.php?pid=2570
 
混乱する.
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2822    Accepted Submission(s): 966
Problem Description
崖のyifenfeiを通って、また幽谷の試練に直面しています.
幽谷の周囲は瘴気に満ちていて、静かで恐ろしくて、かすかに地面に骸骨が積み上げられているのが見えます.ここは長い間空が見えないため、空気中に毒素がいっぱい入っていて、体内に吸い込むと全身が潰れて死んでしまいます.
幸いyifenfeiは防備が早く、解薬材(各種濃度の万能薬水)を事前に用意していた.現在は異なる割合の濃度に配置するだけです.
現在、yifenfeiはn種濃度の万能薬水を携帯しており、体積Vはいずれも同じであり、濃度はそれぞれPi%であることが知られている.また,当時の幽谷の瘴気に対しては,万能薬水の一部または全部を選択し,W%以下の濃度の薬水を配置するだけで解毒できることが分かった.
現在の問題は、この薬をどのように配置すれば、現在使用可能な解薬を最大体積で得ることができるかということです.
特に、幽谷内の設備の制限により、既存の1つの薬をすべて別の薬に混入させることしか許されない(すなわち、1つの薬に対してその一部だけを取るという操作は現れない).

 
 
Input
入力データの最初の行は整数Cであり、テストデータのグループ数を表す.
各試験データは2行を含み、まず1行は3つの正の整数n,V,W(1<=n,V,W<=100)を与える.
次の行はn個の整数であり、n種類の薬水の濃度Pi%(1<=Pi<=100)を示す.
 
 
Output
各テストデータのセットについて、整数と浮動小数点数を出力します.
このうち整数は解薬の最大体積を表し、浮動小数点数は解薬の濃度を表す(四捨五入は2桁の小数を保留する).
要件を満たす解薬が配合できない場合は、0 0.00を出力してください.
 
 
Sample Input
3 1 100 10 100 2 100 24 20 30 3 100 24 20 20 30
 
 
Sample Output
 
#0 0.00
100 0.20
300 0.23
 
 
Author
yifenfei
 
 
Source
ACMプログラム設計期末試験081230
 
 
Recommend
yifenfei
 
 
構想:n瓶が互いに配合した後の濃度は  (p1*v+p2*v+p3*v.....+pn*v)/n*v  すなわち(p 1+p 2+.....pn)/n;
濃度を並べ替えて   小さい時から大きい時まで   そしてこんな和を求めて     最大でいくつか参加できるか見てみましょう
コードを見て水はもう水にならない   

#include<stdio.h>

#include<algorithm>

using namespace std;

int a[1000],sum[1000];

int main()

{

    int i,cas,n,v ,p;

    double ap;

    scanf("%d",&cas);

    while(cas--)

    {

         scanf("%d %d %d",&n,&v,&p);

         sum[0]=0;

         ap=0;

         for(i=1;i<=n;i++) {scanf("%d",&a[i]);}

         sort(a+1,a+1+n);

         for(i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];

        // printf("ca");

         for(i=1;i<=n;i++)

         {

            double mid=(double)sum[i]/i;

             if(mid<=(double)p)

                 ap=mid; 

             else break;

         }

         printf("%d %.2lf
",(i-1)*v,ap/100);

    }

    return 0;

}