本文共 3406 字，大约阅读时间需要 11 分钟。

1、找零钱

*问题描述*	有n个人正在饭堂排队买海北鸡饭。每份海北鸡饭要25元。奇怪的是，每个人手里只有一张钞票（每张钞票的面值为25、50、100元），而且饭堂阿姨一开始没有任何零钱。请问饭堂阿姨能否给所有人找零（假设饭堂阿姨足够聪明）*输入格式*　　第一行一个整数n，表示排队的人数。　　接下来n个整数a[1],a[2],...,a[n]。a[i]表示第i位学生手里钞票的价值（i越小，在队伍里越靠前）输出格式　　输出YES或者NO样例输入425 25 50 50样例输出YES样例输入225 100样例输出NO样例输入425 25 50 100样例输出YES

import java.util.Scanner;public class Money {
   	static int n;	static int[] b=new int[101]; //用b[25],b[50],b[100]分别记录可以找出的该面值钞票数量	public static void main(String[] args) {
   				Scanner sc = new Scanner(System.in);		n=sc.nextInt();		int[] a=new int[n+1];			for(int i=1;i<=n;i++){
   			a[i]=sc.nextInt();	//第i个人钞票的面值		}		for(int i=1;i<=n;i++) {
   			switch(a[i]) {
   		//用switch对第i个人钞票面值进行判断			case 25:				b[25]++;		//25数量++				break;			case 50:				if(b[25]<1) {
   	//判断是否可以找零					System.out.println("NO");					return;				}else {
   					b[25]--;	//找出25					b[50]++;	//50数量++					break;				}			case 100:				if(b[50]>=1 && b[25]>=1) {
   //判断是否可以用50和25找零					b[50]--;					b[25]--;					b[100]++;				}else if(b[25]>=3) {
   	//若不满足，退而求其次用3个25找零					b[25]-=3;					b[100]++;				}else {
   					//无法找零					System.out.println("NO");					return;				}			}		}		System.out.println("YES");		//可以将for执行完即可以全部找零	}}

同类型

来看一个找零钱的例子，在我国广泛使用的硬币的面额是1元、5角、1角、5分、2分、1分（当然现在没有分了）。假如某顾客买完东西，现在要找给他 9分钱，要求找出的硬币个数最少，那么如何用这些面额的硬币找零呢？这里，采用的方法是：首先选出一个面值不超过 9 分的最大硬币，即 5分钱硬币；从 9 分中减去 5 分，剩下 4 分，再选出一个面值不超过 4 分的最大硬币，即 2 分硬币；从 4 分中减去 2 分，剩下2 分，最后选出一个面值不超过 2 分的最大硬币，即 2 分硬币。用一个公式即可表示为 9 = 5+2+2，总计找出的硬币个数为 3 。

public class Tanxin1 {
   	int i;	static int n=5;	double m=6;	double m1=6;	public static void main(String[] args) {
   		double[] V=new double[] {
   				1,0.5,0.1,0.05,0.02,0.01		};		int[] X=new int[6];		Tanxin1 p=new Tanxin1();		X=p.Greedy(V);		int s=X[0]+X[1]+X[2]+X[3]+X[4]+X[5];		System.out.println("得到找零钱的最优解为:X={ "+X[0]+" "+X[1]+" "+X[2]+" "+X[3]+" "+X[4]+" "+X[5]+" }共需要最少"+s+"枚硬币。");			}	private int[] Greedy(double[] C) {
   		int i=0;		double x=0;		double[] S=new double[n+1];		int[] Z=new int[n+1];		for(i=0;i<=n;i++) {
   			if(solution(S)==0) {
   				x=select(C);				if(feasible(S,x)==1)				{
   					S[i]=x;					Z[this.i]++;					m1=((double)((int)(m1*100)-(int)(x*100)))/100;				}			}		}		System.out.println("使用硬币集为:{ "+S[0]+"  "+S[1]+"  "+S[2]+" }");		return Z;	}	private double select(double[] X) {
   		int i=0;		double x=0;		do {
   			X[i]=0;			i++;		}while(X[i]>m1 || X[i]==0);		this.i=i;		x=X[i];		return x;	}	private double feasible(double[] X, double x) {
   		int i;		int j=1;		double y=0;		for(i=0;i<=n;i++) {
   			y=y+X[i];		}		y=y+x;		return j;	}	private double solution(double[] X) {
   		double s=0;		for(int i=0;i<=n;i++) {
   			s=((double)(int)(s*100)+(int)(X[i]*100))/100;		}		if(s==m)			return 1;		else			return 0;	}}

3、石子游戏

问题描述　　石子游戏的规则如下：　　地上有n堆石子，每次操作可选取两堆石子（石子个数分别为x和y）　　并将它们合并，操作的得分记为(x+1)×(y+1)，对地上的石子堆　　进行操作直到只剩下一堆石子时停止游戏。　　请问在整个游戏过程中操作的总得分的最大值是多少？输入格式　　输入数据的第一行为整数n，表示地上的石子堆数；第二行至第n+1行是每堆石子的个数。输出格式　　程序输出一行，为游戏总得分的最大值。样例输入10510519400273091989227814251291927212517254194053样例输出15212676150

import java.util.*;public class Tanxin2 {
       public static void main(String[] args)    {
           Scanner sc=new Scanner(System.in);        int n=sc.nextInt();        long result=0;        long[] stone=new long[n];        for(int i=0;i
   
    0;i--)        {
               result+=(stone[i]+1)*(stone[i-1]+1);            stone[i-1]=stone[i]+stone[i-1];        }        System.out.print(result);    }}
   

转载地址：http://tgrwi.baihongyu.com/