清北学堂2017NOIP冬令营入学测试
P4745 B’s problem(b)
时间: 1000ms / 空间: 655360KiB / Java类名: Main
背景
冬令营入学测试
描述
题目描述
小B生活在一个很奇怪的国家里，这个国家的钱的面值只有可能是25,50,100的。小B最近在做社会实践，这次它选择在一个餐厅里干这件事情。但今天发生了一件有趣的事，这件事情是这个样子的，餐厅里大家都在排队买饭，粗心的打饭阿姨忘记要带零钱，并且所有排队打饭的人只带了一张钱。
具体地，第i个人带了一张面额为ai的钱，为了方便起见，我们规定每个人都想买价值25元的饭盒。阿姨显得不知所措。聪明的小B想到了一个方法，让带了25元的先买饭！这样阿姨就有了更多的零钱去找开一些面值较大的钱。
但这样对于一些人来说仍有可能找不开零钱，小B想知道是否存在一种排队方案，能够对所有人找开零钱。如果可行输出“YES”，否则输出“NO”。
输入格式
第一行一个数n，表示有n个想买饭的人。
接下来一行n个数ai，表示第i个人带着的钱的面额。
输出格式
输出“YES”或者“NO”。
备注
输入样例
3
25 50 100
输出样例
NO
数据范围
对于100%的数据n<=100，ai=25或者50或者100。
设25、50、100的人分别为s25,s50，s100
1.如果s25<s50,那么25的不够给50的找钱，输出NO
2.在枚举每个s100过程中（也就是s100>0），有50的先找1张50和1张25，没有50的就找3张25的，中途如果出现手中25不够用的情况，那么输出NO
#include<cstdio>
#include<iostream>
using namespace std;
int n,a,b,c,x;//a，b，c分别代表手持25、50、100的人的总数
int aa,bb,cc;//分别代表打饭阿姨手中25、50、100元的数量
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&x);
if(x==) a++;
else if(x==) b++;
else c++;
}
aa=a;//25元的不用找钱，打饭阿姨手中多了a张25元
aa-=b;//给每个50找25元钱后剩下几张25
bb=b;//打饭阿姨手中多了b张50元
if(aa<)//25元的不够找
{
cout<<"NO";return ;
}
for(int i=;i<=c;i++)//给每个100的找钱
{
if(bb>)//优先找50元
{
bb--;
aa--;//找一张50和一张25
if(aa<)//25的不够找
{
cout<<"NO";return ;
}
}
else if(aa==)//c还没有枚举完，25元的没了
{
cout<<"NO";return ;
}
else if(aa>)//没有50的找3张25
{
aa-=;
if(aa<)//25的不够了
{
cout<<"NO";return ;
}
}
}
cout<<"YES";return ;
}