蓝桥杯vip测试题-找零钱(解题思路以及解题代码)

第一行一个整数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.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static int danjia = 25;
    static int xianyoudanjia = 0;
    public static void main(String[] args) {
        int n = sc.nextInt();
        int qian[] = new int[n];
        for (int i = 0; i < n; i++) {
            qian[i] = sc.nextInt();
        }

        Boolean bool = true; 
        List<Integer> list = new ArrayList<>(); //利用List存放暂时找不开的人，先去一边排队去。
        //其实这个地方使用队列会更好。为了简便，我就没使用。

        //找钱
        for (int i = 0; i < qian.length; i++) {
            //如果第i个排队的人的钱足够
            if (qian[i] == danjia) {
                xianyoudanjia += qian[i];
            
              //qian[i]>danjia：第i个人有的钱，大于单价，就说明要找钱了
             //(个人的钱 - 单价)=要找的钱，如果食堂阿姨现有的领钱>=要找的钱，说明可以找开
            } else if (qian[i] > danjia && ((qian[i] - danjia) <= xianyoudanjia)) {
                //找钱，找钱时要记得加上25，然后再减
                xianyoudanjia += 25;
                xianyoudanjia -= (qian[i] - danjia);//然后减去找去的钱
            }
            else{
                list.add(qian[i]);
            }
        }
        //找刚才没找开的
        for (int i = 0; i < list.size(); i++) {
            if(xianyoudanjia>=list.get(i)){
                xianyoudanjia -= list.get(i);
                list.remove(i); //找完要移除，因为已经找完第i个人了，剩下的就是没找的
            }else{
                bool = false;
            }
        }
        System.out.println(list.size()==0?"YES":"NO");//判断是否剩下没找钱的人
    }
}

package TestString;

import java.util.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static int danjia = 25;
    static int xianyoudanjia = 0;
    public static void main(String[] args) {
//        int n = sc.nextInt();
//        int qian[] = new int[n];
//        for (int i = 0; i < n; i++) {
//            qian[i] = sc.nextInt();
//        }

        Boolean bool = true;
        List<Integer> list = new ArrayList<>();

        int [] qian = {25,25,25,50,25,25,100,100};
        //找钱
        for (int i = 0; i < qian.length; i++) {
            //如果第i个排队的人的钱足够
            if (qian[i] == danjia) {
                xianyoudanjia += qian[i];
            } else if (qian[i] > danjia && ((qian[i] - danjia) <= xianyoudanjia)) {
                //找钱
                xianyoudanjia += 25;
                xianyoudanjia -= (qian[i] - danjia);
            }
            else{
                list.add(qian[i]);
            }
//            System.out.println("收入："+xianyoudanjia);
        }
//        System.out.println("还剩："+xianyoudanjia+",正在找："+list.size());
        for (int i = 0; i < list.size(); i++) {
            if(xianyoudanjia>=list.get(i)){
                xianyoudanjia -= list.get(i);
                list.remove(i);
            }else{
                bool = false;
            }
        }
//        System.out.println("还剩："+xianyoudanjia+",找不开："+list.size());
        System.out.println(list.size()==0?"Yes":"NO");
    }
}