牛客练习赛20 E-托米历险记

题目描述

这天,托米家的电影院门口排起了长队--因为最新的电影"托米历险记"就要上映了!每个人都有且仅有一张面值为25或50或100元的钞票.一张电影票的价格是25元.托米想知道售票员能否在初始金钱为0并且按排队顺序售票的情况下完成找零.

输入描述:

第一行一个数字n,表示排队的人的数量.
第二行n个数字,第i个数字为ai,表示队伍中第i个人所持有的钞票的面值.

输出描述:

如果售票员能完成找零,输出"YES"(不含引号).
反之输出"NO".

示例1

输入

4
25 25 50 50

输出

YES

示例2

输入

4
50 50 25 25

输出

NO

备注:

1≤n≤105

#include <iostream>
#include <stack>
using namespace std;
int main() {
    stack<int> s;
    int n, flag, x;
    flag = 0;
    cin>>n;
    for(int i = 0; i < n; i++) {
    	cin>>x;
    	if(x == 25) {
    		s.push(x);
    	} else {
    		if(s.empty()) {
    			flag = 1;
    			break;
    		}
    		x -= 25;
    		while(x) {
        		if(s.empty()) {
    				flag = 1;
    				break;
    			}			
    			x -= s.top();
    			s.pop();
    		}
    	}
    }
    if(flag) {
    	cout<<"NO"<<endl;
    } else {
    	cout<<"YES"<<endl;
    }
    return 0;
}