The new "Die Hard" movie has just been released! There are
n people at the cinema box office standing in a huge line. Each of them has a single100,50 or
25 ruble bill. A "Die Hard" ticket costs25 rubles. Can the booking clerk sell a ticket to each person and give the change if he initially has no money and sells the tickets strictly in the order people
follow in the line?
The first line contains integer n
(1 ≤ n ≤ 105) — the number of people in the line. The next line containsn integers, each of them equals25,
50 or 100 — the values of the bills the people have. The numbers are given in the order from the beginning of the line (at the box office) to the end of the line.
Print "YES" (without the quotes) if the booking clerk can sell a ticket to each person and give the change. Otherwise print "NO".
4 25 25 50 50
YES
2 25 100
NO
4 50 50 25 25
NO
题意：
现在只有25、50、100面值的卢布，已知队伍中每个人身上所带的卢布，且售票员刚开始没有零钱，告诉问能否按队伍次序售完票，并给每个买票的人找钱。
思路：
直接对三种情况模拟。
/*************************************************************************
> File Name: E.cpp
> Author: BSlin
> Mail:
> Created Time: 2013年10月02日 星期三 13时08分04秒
************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <iterator>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#define MP make_pair
#define INF (1<<30)
#define PI acos(-1.0)
#define esp 1e-8
const int dx[4]={0,0,0,0};
using namespace std;
#define read freopen("in.txt","r",stdin)
#define write freopen("out.txt","w",stdout)
#if defined (_WIN32) || defined (__WIN32) || defined (WIN32) || defined (__WIN32__)
#define LL __int64
#define LLS "%" "I" "6" "4" "d"
#else
#define LL long long
#define LLS "%" "l" "l" "d"
#endif
int main(int argc, char** argv) {
//read;
int n,x,flag;
int num[5];
while(scanf("%d",&n) != EOF) {
num[0] = num[1] = num[2] = 0;
flag = 1;
for(int i=0; i<n; i++) {
scanf("%d",&x);
if(i==0 && x != 25) {
flag = 0;
}
else {
if(x == 25) {
num[0] ++;
}
else if(x == 50) {
num[0] --;
num[1] ++;
}
else if(x == 100) {
num[2] ++;
if(num[1] >= 1 && num[0] >= 1) {
num[1] --;
num[0] --;
} else if(num[0] >= 3) {
num[0] -=3;
} else flag = 0;
}
}
if(num[0] < 0 || num[1] < 0 || num[2] < 0) {
flag = 0;
}
}
if(flag == 0) {
printf("NO\n");
}
else printf("YES\n");
}
return 0;
}