HDOJ-ACM1009(JAVA) (传说中的贪心算法)分为数组实现 和 封装类实现
2024-10-18 20:23:23
转载声明:原文转自: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;
} } }
最新文章
- 网址http换成https ----js
- jQuery页面顶部下拉广告
- effective OC2.0 52阅读笔记(七 系统框架)
- C++ 类的静态成员及静态成员函数
- BZOJ1485: [HNOI2009]有趣的数列
- 【Spring】搭建最简单的Spring MVC项目
- ASP.NET跨服务器上传文件的相关解决方案
- [转]VS2015 cordova尝试-camera
- python3中文字符编码问题
- Padding Borders Outlines Margins
- webpack和webpack-dev-server安装配置(遇到各种问题的解决方法)
- 关于dropout的有趣的进化论解释
- 高可用Redis(十):Redis原生命令搭建集群
- unittest批量执行测试用例
- 帆软报表(finereport)安装/配置
- git忽略对已入库文件的修改
- bind啊你返回的函数到底是个虾米
- MFC 不同窗体之间变量调用
- Http协议响应状态类别及说明
- Java MVC和三层架构
热门文章
- 《c程序设计语言》读书笔记-字符型0-9转为数字0-9
- [HIHO1176]欧拉路&#183;一(欧拉图判定)
- hibernate的各种保存方式的区别 (save,persist,update,saveOrUpdte,merge,flush,lock)等
- 【温故知新】c#异步编程模型(APM)--使用委托进行异步编程
- c#快捷键大全
- HDU 2516 (Fabonacci Nim) 取石子游戏
- LA 3902 Network
- Codeforces 424 B Megacity【贪心】
- ui/ue设计师应该了解的原型设计软件
- singleton单例模式