游客 注册 | 登录
中文 | En

1660 - FatMouse's Trade

通过次数

0

提交次数

0

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

FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.

The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i] a% pounds of JavaBeans if he pays F[i] a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain. 

<br />

题目输入

The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1's. All integers are not greater than 1000.


题目输出

For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.


输入/输出样例

输入格式

4 2
4 7
1 3
5 5
4 8
3 8
1 2
2 5
2 4
-1 -1

输出格式

2.286
2.500

C语言解答

#include <stdio.h>
int main()
{
  int m,n,i=0,t=0; 
  double j[1000],f[1000],sum=0;
  while(scanf("%d %d",&m,&n)!=EOF && m+n>0) 
  {
   for(i=0;i<n;i++)
   {
        scanf("%lf %lf",&j[i],&f[i]);          
   }
   for(i=0;i<n;i++)
   {
       for(t=0;t<n;t++)
       {
           if(j[i]/f[i]>j[t]/f[t])
           {
                 double temp;
                   temp=j[i];
                   j[i]=j[t];  
                   j[t]=temp;
                    
                   temp=f[i];
                   f[i]=f[t];  
                   f[t]=temp;
           }
       }
   }
   for(i=0;i<n;i++)
   {
      if(m<f[i])
      {
         sum+=m*j[i]/f[i];
         break;
      }
      else
      {
          sum+=j[i];
          m-=f[i];
      }
   }
   printf("%.3f\n",sum);
   sum=0;
}
  return 0;
}

C++解答

//注意m和f可以为0 
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string.h>
#include <queue>
#include <stdlib.h>
using namespace std;

typedef struct node
{
	int j;
	int f;
	double d;
}MC;
MC a[1003];

bool cmp(MC a,MC b)
{
	return a.d>b.d;
}

int main()
{
	int n,m,i;
	double t;
	while(scanf("%d%d",&n,&m))
	{
		if(n==-1&&m==-1)
			break;
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&a[i].j,&a[i].f);
			a[i].d=1.0*a[i].j/a[i].f;
		}
		sort(a,a+m,cmp);
		t=0;
		for(i=0;i<m;i++)
		{
			if(n>a[i].f)
			{
				t+=a[i].j;
				n-=a[i].f;
			}
			else
			{
				t+=n*a[i].d;
				break;
			}
		}
		printf("%.3lf\n",t);
	}
	return 0;
}

Java解答

import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;



class Main {
	private static Scanner scan=new Scanner(System.in);
	public static void main(String[] args) {
		boolean flag=true;
		List<Double> list=new ArrayList<Double>();
		while(flag)
		{
			double a=scan.nextInt();
			int b=scan.nextInt();
			if(a==-1 && b==-1)
			{
				flag=false;
			}
			else 
			{
				double[][] values=new double[b][2];
				
				for (int i = 0; i < b; i++) 
				{
					values[i][0]=scan.nextInt();
					values[i][1]=scan.nextInt();
				}
				for (int i = 0; i < b-1; i++) 
				{
					for (int j = i+1; j < b; j++) 
					{
						if((values[i][0]/values[i][1])<(values[j][0]/values[j][1]))
						{
							double x=values[i][0];
							double y=values[i][1];
							values[i][0]=values[j][0];
							values[i][1]=values[j][1];
							values[j][0]=x;
							values[j][1]=y;
						}
						else if((values[i][0]/values[i][1])==(values[j][0]/values[j][1]) && values[i][0]<values[j][0])
						{
							double x=values[i][0];
							double y=values[i][1];
							values[i][0]=values[j][0];
							values[i][1]=values[j][1];
							values[j][0]=x;
							values[j][1]=y;
						}
					}
				}
				double result=0;
				double stillNum=a;
				for (int i = 0; i < b; i++) 
				{
					if(stillNum<=values[i][1])
					{
						result=stillNum*(values[i][0]/values[i][1])+result;
						list.add(result);
						break;
					}
					else 
					{
						result+=values[i][0];
						stillNum=stillNum-values[i][1];
					}
				}
			}
		}
		DecimalFormat df=new DecimalFormat("0.000");
		
		for (Double s : list) 
		{
			System.out.println(df.format(s));
		}
	}
}
请先登陆