转载声明:原文转自:http://www.cnblogs.com/xiezie/p/5564311.html

这个道题有几点要注意的:

  数组存放的类型:float或double

  打印的格式:(如果只是System.out.printf("%.3f\n",maxF); //会报Presentation Error)另外是:Java 中的printf -----不存在"%lf"这个情况...

System.out.printf("%.3f",maxF);//maxF为输出结果 即最大鼠食
System.out.println();

  还有一点要注意的是如果M值等于一个房间的猫粮的大小时,M不能与F[i]/J[i]相乘,会导致结果出错,

           不过这一点,思路清晰的人应该不会有问题。

以下是JAVA语言实现:

  数组实现的代码:

import java.util.*;
import java.io.*; /**
*数组实现,实现当中运用了快排,具体见static方法
*/
public class Main{ public static void main(String[] arg){
Scanner scan = new Scanner(new BufferedInputStream(System.in));
int m,n;
while((m=scan.nextInt())!=-1&&(n=scan.nextInt())!=-1){
double f[] = new double[n];//鼠食
double j[] = new double[n];//猫粮
double a[] = new double[n];
double maxF=0;
for(int i =0 ; i != n ; i ++){
f[i] = scan.nextDouble();
j[i] = scan.nextDouble();
a[i] = f[i]/j[i];
}
sort(a,f,j);
for(int i =n-1 ; i !=-1 ; i -- ){
if(m>=j[i]){//这里必须打等于号 不然会导致结果不准确 ACM会WA
m -= j[i];
maxF += f[i];
}else{
maxF += m*a[i];
break;
}
}
System.out.printf("%.3f",maxF);
System.out.println();
}
scan.close();
} static void sort(double[] a,double[] b,double[] c) {
int len = a.length;
int low = 0,high = len - 1;
quickSort(a,b,c, low, high);
} static void quickSort(double[] a,double[] b, double[] c,int l ,int h){
if(l>=h){
return;
}
int low = l;
int high = h;
double k = a[low];
double k2 = b[low];
double k3 = c[low];
while(low< high){
//
while(high>low&&a[high]>=k){//寻找元素右边比其小的
high --;
}
a[low] = a[high];//进行交换,K指向high
b[low] = b[high];
c[low] = c[high];
while(low<high&&a[low]<=k){//寻找元素左边比其大的
low++;
}
a[high] = a[low];//进行交换,K指向low
b[high] = b[low];
c[high] = c[low];
}
a[low] = k;//将K赋给low
b[low] = k2;
c[low] = k3;
quickSort(a,b, c,l, low-1);
quickSort(a,b, c,low+1, h);
} }

为了体现JAVA的OOP实现,我还写了用类实现的方法

以下是封装类实现的代码:

import java.util.*;
import java.io.*; public class Main{ public static void main(String[] arg){
Scanner scan = new Scanner(new BufferedInputStream(System.in));
int m,n;
while((m=scan.nextInt())!=-1&&(n=scan.nextInt())!=-1){
ArrayList<Trade> trades = new ArrayList<>(n);
double maxF=0;
for(int i =0 ; i != n ; i ++){
Trade trade = new Trade();
trade.setF(scan.nextDouble());
trade.setJ(scan.nextDouble());
trades.add(trade);
}
Collections.sort(trades);
for(int i =0 ; i !=n ; i ++ ){
Trade trade = trades.get(i);
if(m>= trade.getJ() ){
m -= trade.getJ() ;
maxF += trade.getF() ;
}else{
maxF += m*trade.getA();
break;
}
}
System.out.printf("%.3f",maxF);
System.out.println();
}
scan.close();
} static class Trade implements Comparable<Trade> {
private double f;//鼠食
private double j;//猫粮 @Override
public int compareTo(Trade o) {
if(getA()>o.getA()){
return -1;
}else if(getA()==o.getA()){
return 0;
}
return 1;
} public double getF() {
return f;
} public void setF(double f) {
this.f = f;
} public double getJ() {
return j;
} public void setJ(double j) {
this.j = j;
} public double getA() {//获取性价比
return f/j;
} } }

最新文章

  1. 网址http换成https ----js
  2. jQuery页面顶部下拉广告
  3. effective OC2.0 52阅读笔记(七 系统框架)
  4. C++ 类的静态成员及静态成员函数
  5. BZOJ1485: [HNOI2009]有趣的数列
  6. 【Spring】搭建最简单的Spring MVC项目
  7. ASP.NET跨服务器上传文件的相关解决方案
  8. [转]VS2015 cordova尝试-camera
  9. python3中文字符编码问题
  10. Padding Borders Outlines Margins
  11. webpack和webpack-dev-server安装配置(遇到各种问题的解决方法)
  12. 关于dropout的有趣的进化论解释
  13. 高可用Redis(十):Redis原生命令搭建集群
  14. unittest批量执行测试用例
  15. 帆软报表(finereport)安装/配置
  16. git忽略对已入库文件的修改
  17. bind啊你返回的函数到底是个虾米
  18. MFC 不同窗体之间变量调用
  19. Http协议响应状态类别及说明
  20. Java MVC和三层架构

热门文章

  1. 《c程序设计语言》读书笔记-字符型0-9转为数字0-9
  2. [HIHO1176]欧拉路&#183;一(欧拉图判定)
  3. hibernate的各种保存方式的区别 (save,persist,update,saveOrUpdte,merge,flush,lock)等
  4. 【温故知新】c#异步编程模型(APM)--使用委托进行异步编程
  5. c#快捷键大全
  6. HDU 2516 (Fabonacci Nim) 取石子游戏
  7. LA 3902 Network
  8. Codeforces 424 B Megacity【贪心】
  9. ui/ue设计师应该了解的原型设计软件
  10. singleton单例模式