HDOJ 2570迷瘴

2167 ワード

混乱する.
Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 1   Accepted Submission(s) : 1
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
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

テーマは長くて煩雑に見えますが、簡単な欲張りです.タイトルに要求された四捨五入
特殊な処理を必要とせず、出力の2桁の小数を直接制御すればよい.コンパイラは自分で四捨五入することができる.
コードは次のとおりです.
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int main()
{
	int C,n,v,w,p[1100],sum,i,k;
	double pb,j;
	scanf("%d",&C);
	while(C--)
	{
		scanf("%d%d%d",&n,&v,&w);
		for(i=0;i<n;i++)
			scanf("%d",&p[i]);
		sort(p,p+n);
		sum=0;
		pb=0;
		j=p[0];
		k=p[0];
		for(i=0;i<n;i++)
		{
			if(j<=w)
			{
			   sum=sum+v;
			   pb=(j/100.0);
			   k=k+p[i+1];
			   j=k*1.0/(i+2);//     j           
			}
			else
			  break;
		}
		printf("%d %.2lf
",sum,pb); } return 0; }