|
试题 算法训练 找零钱
问题描述 有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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
public static void main(String[] args) throws Exception, IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(br.readLine());
String []arr=br.readLine().split(" ");
boolean flat=true;
List list=new ArrayList();
int a[]=new int[arr.length];
for (int i = 0; i
if (a[i]==25) {
list.add(a[i]);
}else if (a[i]==50&&list.contains(25)) {
list.add(a[i]);
list.remove(Integer.valueOf(25));
}else if (a[i]==100&&list.contains(25)&&list.contains(50)) {
list.add(a[i]);
list.remove(Integer.valueOf(25));
list.remove(Integer.valueOf(50));
}else if (a[i]==100&&list.size()>3&&list.contains(25)&&list.get(2)==25) {
list.add(a[i]);
list.remove(Integer.valueOf(25));
list.remove(Integer.valueOf(25));
list.remove(Integer.valueOf(25));
}else {
flat=false;
break;
}
}
System.out.println(flat?"YES":"NO");
}
}
|