算法训练 找零钱

0
8

资源限制
时间限制: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

需要多种情况的考虑,即25,50和100元的三种情况。

 1 #include<iostream>
 2 //author:QIANG
 3 using namespace std;
 4 int main(){
 5     int n,s;
 6     cin>>n;
 7     int tf=0,f=0;
 8     int flag=1;
 9     for(int i=0;i<n;i++){
10         cin>>s;
11         if(flag==1){
12             if(s==25){
13                 tf++;
14             }else if(s==50){
15                 if(tf>0){
16                     tf--;
17                     f++;
18                 }else{
19                     flag=0;
20                 }
21             }else{
22                 if(f>0){
23                     f--;
24                     s=s-50;
25                 }
26                 if(s==50){
27                     if(tf>0){
28                         tf--;
29                     }else{
30                         flag=0;
31                     }
32                 }else{
33                     if(tf>=3){
34                         tf=tf-3;
35                     }else{
36                         flag=0;
37                     }
38                 }
39             }
40         }
41     }
42     if(flag==1){
43         cout<<"YES";
44     }else cout<<"NO";
45     return 0; 
46 } 

<

发布回复

请输入评论!
请输入你的名字