13518219792
题分析：
成都创新互联专注为客户提供全方位的互联网综合服务，包含不限于网站建设、成都网站制作、班戈网络推广、小程序定制开发、班戈网络营销、班戈企业策划、班戈品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们最大的嘉奖；成都创新互联为所有大学生创业者提供班戈建站搭建服务，24小时服务热线：13518219792，官方网址：www.cdcxhl.com
根据常识，我们到店里买东西找钱时，老板总是先给我们最大面值的，要是不够再找面值小一点的，直到找满为止。如果老板都给你找分数的或者几角的，那你肯定不干，另外，他也可能没有那么多零碎的钱给你找。其实这就是一个典型的贪心选择问题。
问题的算法设计与实现：
先举个例子，假如老板要找给我99分钱，他有上面的面值分别为25，10，5，1的硬币数，为了找给我最少的硬币数，那么他是不是该这样找呢，先看看该找多少个25分的，诶99／25＝3，好像是3个，要是4个的话，我们还得再给老板一个1分的，我不干，那么老板只能给我3个25分的拉，由于还少给我24，所以还得给我2个10分的和4个1分。
具体实现
Code:
//找零钱算法//By falcon//输入：数组m，依次存放从大到小排列的面值数，n为需要找的钱数，单位全部为分//输出：数组num，对照数组m中的面值存放不同面值的硬币的个数，就找钱方案 public static int[] zhaoqian(int m[],int n) { int k=m.length; int[] num=new int[k]; for(int i=0;ik;i++) { numi=n/mi; n=n%mi; } return num; }
[Ctrl+A Select All]
演示代码
Code:
public class zhaoqian{ public static void main(String[] args) { int m[]={25,10,5,1}; int n=99; int[] num=new int[m.length]; num=zhaoqian(m,n); System.out.println(n+"的找钱方案："); for(int i=0;im.length;i++) System.out.println(numi+"枚"+mi+"面值"); } public static int[] zhaoqian(int m[],int n) { int k=m.length; int[] num=new int[k]; for(int i=0;ik;i++) { numi=n/mi; n=n%mi; } return num; }}
[Ctrl+A Select All]
演示结果：
falcon@falcon:~/program/java$ javac zhaoqian.java
falcon@falcon:~/program/java$ java zhaoqian
99的找钱方案：
3枚25面值
2枚10面值
0枚5面值
4枚1面值
第一、你说的那个东西不叫框架
第二、你用的算法不是多路合并
第三、题目不是让你合并、是让你找出最优解
解答，我晕这题目有啥解答的啊，你不是自己编的吧，假如合并两个有序序列只要m+n-1次比较，那么不单单这两个序列各自有序，同时其中一个序列任意元素大于另外一个序列所有元素
那么答案就是按照k的序号从前想后依次合并啊
public getMin{
public int MinNumber=0;
public int findMax(int[] a){
for(int i=0;ia.length;i++){
if(a[i]==0) return a[--i];
}
return a[a.length-1];
}
public boolean Compare(int a,int b){
public boolean flag=true;
if(ab) flag=flase;
return flag;
}
public int getMinNumber(int[] M,int Money){
int[] findM=new int[M.length];
int index=0;
for(int i=0;iM.length;i++){
boolean f = this.Compare(M[i],money)
if(f) findM[index++]=M[i];
}
int max = this.findMax(findM);
MinNumber++;
if((Money-max)!=0) {
getMinNumber(M,Money-max)
}
return MinNumber;
}
public int[] Start(){
System.out.println("请输入查询组数");
int group=System.in.read();
int[] M={1,2,5,10,20,50,100};
int[] Result = new Int[group];
int index=0;
while (group-- 0){
System.out.println("请输入金额");
int money=System.in.read();
Result[index++] = getMinNumber(M,money);
MinNumber=0;
}
}
public void print(int[] MinNumber){
for(int i=0;iMinNumber.length.i++){
System.out.println(MinNumber[i]+" ");
}
}
}
public static void main(String[] args){
new getMin().print(new getMin().Start());
}
没测试啊，有问题请勿喷，呵呵
贪心算法: 思路就是对花到第一个喷泉距离从近到远排序，然后找到另一个喷泉距离最大的一个
复杂度O(n^2)。
import java.util.*;
public class Demo {
static long[][] flowers;
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int x1=in.nextInt();
int y1=in.nextInt();
int x2=in.nextInt();
int y2=in.nextInt();
flowers=new long[n][2];
for (int i = 0; i n; i++) {
int x=in.nextInt();
int y=in.nextInt();
flowers[i][0]=dis(x,y,x1,y1);
flowers[i][1]=dis(x,y,x2,y2);
}
Arrays.sort(flowers, (o1, o2) - {
if (o1[0]o2[0])
return -1;
else if (o1[0]==o2[0])
return 0;
else return 1;
});
long temp=0;
long temp2=0;
for (int i = 0; i flowers.length; i++) {
temp=Math.max(temp,flowers[i][1]);
}
for (int i = 0; i flowers.length; i++) {
for (int j = i+1; j flowers.length ; j++) {
if (flowers[j][1]temp2)
temp2=flowers[j][1];
}
temp=Math.min(temp,flowers[i][0]+temp2);
temp2=0;
}
System.out.println(temp);
}
public static long dis(int x,int y,int x1,int y1){
return (long) (x1 - x) *(x1-x)+ (long) (y1 - y) *(y1-y);
}
}
