Java实现蓝桥杯算法训练找零钱

小灰灰 2023-07-25 09:44 25阅读 0赞

## 试题 算法训练 找零钱 ##

问题描述  
　　有n个人正在饭堂排队买海北鸡饭。每份海北鸡饭要25元。奇怪的是，每个人手里只有一张钞票（每张钞票的面值为25、50、100元），而且饭堂阿姨一开始没有任何零钱。请问饭堂阿姨能否给所有人找零（假设饭堂阿姨足够聪明）  
输入格式  
　　第一行一个整数n，表示排队的人数。

接下来n个整数a\[1\],a\[2\],…,a\[n\]。a\[i\]表示第i位学生手里钞票的价值（i越小，在队伍里越靠前）  
输出格式  
　　输出YES或者NO  
样例输入  
4  
25 25 50 50  
样例输出  
YES  
样例输入  
2  
25 100  
样例输出  
NO  
样例输入  
4  
25 25 50 100  
样例输出  
YES  
数据规模和约定  
　　n不超过1000000

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class Main { 
    	public static void main(String[] args) throws Exception, IOException { 
    		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    		int n=Integer.parseInt(br.readLine());
    		String []arr=br.readLine().split(" ");
    		boolean flat=true;
    		List<Integer> list=new ArrayList<Integer>();
    		int a[]=new int[arr.length];
    		for (int i = 0; i < a.length; i++) { 
    			a[i]=Integer.parseInt(arr[i]);
    		}
    		Arrays.sort(a);
    		for (int i = 0; i < a.length; i++) { 
    			if (a[i]==25) { 
    				list.add(a[i]);
    			}else if (a[i]==50&&list.contains(25)) { 
    				list.add(a[i]);
    				list.remove(Integer.valueOf(25));
    			}else if (a[i]==100&&list.contains(25)&&list.contains(50)) { 
    				list.add(a[i]);
    				list.remove(Integer.valueOf(25));
    				list.remove(Integer.valueOf(50));
    			}else if (a[i]==100&&list.size()>3&&list.contains(25)&&list.get(2)==25) { 
    				list.add(a[i]);
    				list.remove(Integer.valueOf(25));
    				list.remove(Integer.valueOf(25));
    				list.remove(Integer.valueOf(25));
    			}else { 
    				flat=false;
    				break;
    			}
    		}
    		System.out.println(flat?"YES":"NO");
    	}
    }