游客 注册 | 登录
中文 | En

1668 - 迷瘴

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB 


小明正在玩游戏，他控制的角色正面临着幽谷的考验——<br />

幽谷周围瘴气弥漫，静的可怕，隐约可见地上堆满了骷髅。由于此处长年不见天日，导致空气中布满了毒素，一旦吸入体内，便会全身溃烂而死。
幸好小明早有防备，提前备好了解药材料（各种浓度的万能药水）。现在只需按照配置成不同比例的浓度。
现已知小明随身携带有n种浓度的万能药水，体积V都相同，浓度则分别为Pi%。并且知道，针对当时幽谷的瘴气情况，只需选择部分或者全部的万能药水，然后配置出浓度不大于 W%的药水即可解毒。
现在的问题是：如何配置此药，能得到最大体积的当前可用的解药呢？
特别说明：由于幽谷内设备的限制,只允许把一种已有的药全部混入另一种之中（即：不能出现对一种药只取它的一部分这样的操作）。 

<br />

题目输入


输入数据的第一行是一个整数C，表示测试数据的组数；<br />

每组测试数据包含2行，首先一行给出三个正整数n,V,W(1<=n,V,W<=100)；
接着一行是n个整数，表示n种药水的浓度Pi%(1<=Pi<=100)。 

<br />

题目输出


对于每组测试数据，请输出一个整数和一个浮点数；<br />

其中整数表示解药的最大体积，浮点数表示解药的浓度(四舍五入保留2位小数)；
如果不能配出满足要求的的解药，则请输出0 0.00。 

<br />

输入/输出样例

输入格式

2
1 35 68
1 
2 79 25
59 63

输出格式

35 0.01
0 0.00

C语言解答

#include <stdio.h>
#include<string.h>
#include<math.h>
#define maxn 100
int main()
{
	int c, n, i, j;
	double v = 0, w = 0, tmp = 0;
	double y = 0, ar[maxn];
	memset(ar, 0, sizeof(ar));
	scanf("%d", &c);
	while (c)
	{
		i = 0;
		scanf("%d %lf %lf", &n, &v, &w);
		while (i<n)
		{
			scanf("%lf", &ar[i]);
			i++;
		}
		for (i = 0; i<n; i++)
		{
			for (j = 0; j<n; j++)
			{
				if (ar[i]<ar[j])
				{
					int t = ar[j];
					ar[j] = ar[i];
					ar[i] = t;
				}
			}
		}
		j = 0;
		for (i = 0; i<n;i++)
		{
			tmp = ar[i] * v;
			if ((y + tmp) / (double)(v*(i + 1)) <= w)
			{
				y = y + tmp;
				j++;
			}
			else
			{
				break;
			}
		}
		if (j==0)
		{
			y = 0;
		}
		else
		{
		   y = y / (v*j);
		   int p = y;
		   if (y-(double)p>=0.5)
		   {
			  y += 0.5;
		   }
		}

		printf("%d %.2f\n", (int)(v*j),y / 100.0);
		y = 0.0;
		c--;
	}
	return 0;
}

C++解答

#include<stdio.h>
#include<stdlib.h>

int cmp(const void *a,const void *b){
	return *((int*)a)-*((int*)b);
}

int main(){
	int i,n,v,w,cnt;
	double now;
	int as[109],cas;
	scanf("%d",&cas);
	while( cas-- ){
		scanf("%d%d%d",&n,&v,&w);
		now=0;
		cnt=0;
		for( i=0; i<n; i++ )
			scanf("%d",as+i);
		qsort(as,n,sizeof(as[0]),cmp);
		for( i=0; i<n; i++ ){
			if( now+as[i] > (cnt+1)*w )
				break;
			else
				now+=as[i],cnt++;
		}
		if( cnt )
		now=now/cnt/100;
		printf("%d %.2lf\n",cnt*v,now);
	}
	return 0;
}

Java解答


import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.Scanner;


class Main {
	
	private static Scanner scan=new Scanner(System.in);
	public static void main(String[] args) 
	{
		// TODO Auto-generated method stub
		int num=scan.nextInt();
		double[][] values=new double[num][2];
		for (int i = 0; i < num; i++) 
		{
			int n=scan.nextInt();
			int V=scan.nextInt();
			int W=scan.nextInt();
			int[] Pi=new int[n];
			for (int j = 0; j < n; j++) 
			{
				Pi[j]=scan.nextInt();
			}
			Arrays.sort(Pi);
			if(Pi[0]>W)
			{
				values[i][0]=0;
				values[i][1]=0.00;
			}
			else if(n==1)
			{
				values[i][0]=V;
				values[i][1]=(double)Pi[0]/100;
			}
			else
			{
				double result=0.00;
				int count=0;
				for (int j = 0; j < n; j++) 
				{
					if((result + Pi[j]) <= (W * (j + 1)))
					{
						result+=Pi[j];
						count++;
					}
					else 
					{
						break;
					}
				}
				values[i][0]=V*count;
				values[i][1]=result/(count*100);
			}
		}
		DecimalFormat df=new DecimalFormat("0.00");
		for (int i = 0; i < num; i++)
		{
			String s=df.format(values[i][1]);
			System.out.println((int)values[i][0]+" "+s);
		}
	}

}
请先登陆