蓝桥杯试题算法训练找零钱

我会带着你远行 2021-09-24 00:32 384阅读 0赞

试题 算法训练 找零钱

资源限制  
时间限制：1.0s 内存限制：256.0MB  
问题描述  
　　有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.util.Scanner;
    
    public class Main { 
    
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int rw=0,ws=0;
            boolean f = true;
            for (int i = 0; i < n; i++) { 
                int s = sc.nextInt();
                if (f)
                { 
                    if (s==25) { 
                        rw++;
                    }
                    else if(s==50)
                    { 
                        if (rw>0)
                        { 
                            rw--;
                            ws++;
                        }
                        else
                        { 
                            f=false;
                        }
                    }
                    else //收到100的情况
                    { 
                        if (ws>0)
                        { 
                            s=s-50;
                        }
                        if (s==50)
                        { 
                            if (rw>0) { 
                                rw--;
                            }else
                            { 
                                f=false;
                            }
                        }
                        else
                        { 
                            if (rw>=3) { 
                                rw-=3;
                            }
                            else
                            { 
                                f=false;
                            }
                        }
                    }
                }
            }
            if (f) System.out.println("YES");
            else System.out.println("NO");
        }
    }