蓝桥杯练习系统算法训练： ALGO-232 找零钱（贪心）

╰半橙微兮° 2023-07-14 10:51 2阅读 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

样例输出

样例输入

4  
25 25 50 100

样例输出

YES

数据规模和约定

n不超过1000000

解题思路：主要考察了贪心算法的运用，第一次写的时候没有考虑全面，导致只过了一半的测试样例。因为面额只有25、50、100三种面额，如果给了阿姨100元，先减去25，剩下的是阿姨真正需要找的钱。所以100元先减去25元剩下了75，先用50的，如果50的钱还有那么就先找给他50，再找给他25就找开了。但是没有50的钱的时候只能用25的找，所以不应该只减去一次25，应该是只要还有25面额的钱就减去25，直到25的也没有了才算是找钱失败。比如输入的是：25 25 25 100。

AC代码：

#include<iostream>
    using namespace std;
    
    int a[1000001];
    int main(){
    	int n;
    	int m25 = 0,m50 = 0,m100 = 0;    //分别用来存储阿姨手里各个面额的数量 
    	//输入 
    	cin>>n;
    	for(int i=0;i<n;i++){
    		cin>>a[i];
    	}
    	//阿姨手中一开始没有零钱，所以第一个不是25就找不开 
    	if(a[0]!=25){
    		cout<<"NO"<<endl;
    	}else{
    		bool flag = true;  //用来标记钱数能不能找开 
    		//首先统计阿姨收到的钱数 
    		for(int i=0;i<n;i++){
    			if(a[i]==25)  m25++;
    			else if(a[i]==50)  m50++;
    			else m100++; 
    			
    			//首先将每个人付的钱减去25，这才是阿姨需要找的零钱
    			a[i] -= 25;
    			//然后开始找零钱 
    			//钱数不会超过100 
    			if(a[i]==75 && m50){
    				a[i] -= 50;
    				m50--;
    			}
    			//考虑不全面，比如：25 25 25 100 
    //			if(a[i]==25 && m25){
    //				a[i] -= 25;
    //				m25--;
    //			}
    			while(a[i] > 0 && m25){
    				a[i] -= 25;
    				m25--;
    			}
    			//cout<<a[i]<<endl; 
    			if(a[i]){
    				//如果最后的钱数不为0，说明没有找开钱 
    				flag = false;
    				break;
    			}
    			
    		}
    		if(flag){
    			cout<<"YES";
    		}else{
    			cout<<"NO";
    		}
    		
    	} 
    	
    	return 0; 
    	
    }