hdu 2570迷瘴(貪欲)

混乱する.
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4853    Accepted Submission(s): 1654
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   |   We have carefully selected several similar problems for you:   2571  2569  2567  2568  2572 
 
Statistic |  Submit |  Discuss |  Note
ああ、TM精度の問題 頭が破れても思いもよらなかった...何度も
また、濃度公式を事前に書くべきで、頭で空想するのはずっと正道ではありません.

#include <stdio.h>
#include <algorithm>
using namespace std;
int main()
{
    int ncase,n;
    double a[105],w,v;
    scanf("%d",&ncase);
    while(ncase--)
    {
        scanf("%d %lf %lf",&n,&v,&w);
        for(int i=0;i<n;i++)
        scanf("%lf",&a[i]);
        sort(a,a+n);
        if(a[0]>w)
        {
            printf("0 0.00
");
            continue;
        }
        double sum=0;
        int i;
        for(i=0;i<n;i++)
        {
            if((sum+a[i]/100*v)/((i+1)*v)-0.00001<=w/100)
            sum+=a[i]*v/100;
            else
            break;
        }
        printf("%.lf %.2lf
",i*v,sum/i/v);
    }
    return 0;
}