HDU 2570迷瘴(欲張りプロセスの処理が悪いと精度の問題になる)

混乱する.
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
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
   
   
   
   

 
/************************************************************************/
大体言って、n種類の体積Vはすべて同じで、濃度はPi%の万能の薬水で、できるだけ多くの万能の薬水を選んで混合して、混合した後の濃度≦W%を満たす必要があります.
問題の構想を解く:間違いなく、この問題は貪欲な問題で、できるだけ多くの万能薬を選ぶことができるため、私たちはまず濃度が低いものを選んで、混合後の濃度を下げる作用を達成することができます.
従って、まず万能薬水を濃度順に並べ、現在の万能薬水を添加すると混合後の濃度がW%を超えるか否かを小さいから大きいまで一つ一つ判断すればよい.
なお、比較濃度がW%を超えているか否かを比較する過程で濃度を溶質質量に変換して比較すると、x>wを判断する際には、x-0.00001>wと記入して精度エラーが発生しないことを保証しなければならない.そうしないと、以下のコードの書き方でACができる.

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<stdlib.h>
#include<cmath>
#include<string>
#include<algorithm>
#include<iostream>
#define exp 1e-10
using namespace std;
const int N = 105;
const int inf = 2147483647;
const int mod = 2009;
int p[N];
int main()
{
    int t,n,v,w,i;
    double C;
    scanf("%d",&t);
    while(t--)
    {
        C=0;
        scanf("%d%d%d",&n,&v,&w);
        for(i=0;i<n;i++)
            scanf("%d",&p[i]);
        sort(p,p+n);
        for(i=0;i<n;i++)
            if((C+p[i])/(i+1)<=w)
                C+=p[i];
            else
                break;
        if(!i)
            puts("0 0.00");
        else
            printf("%d %.2f
",i*v,C/i/100);
    }
    return 0;
}

菜鳥成長記