codeforces A. Cinema Line 解题报告

题目链接：http://codeforces.com/problemset/problem/349/A

题目意思：题目不难理解，从一开始什么钱都没有的情况下，要向每一个人售票，每张票价格是25卢布，这些人只可能拥有100，50，25的其中一张卢布。问：售票员是否能在可以找赎的情况下，向每一个人都售到票。

此题被贴上贪心的标签，但我觉得更像模拟题。用了比较笨的方法来解决，但是毕竟是自己编的，还是比较有感觉。要特别注意，收了别人的钱，相应的面额数量要作相应的改动。例如第一个样例的25 25 50 50，当处理到第三个人的50时，25卢比这个面值只剩下1了，原因是要找给第三个人25卢比，而本来没有50卢布面额的也从数量0变为1。网上有很多比较简单的方法，以下链接是个人觉得比较巧妙的： http://codeforces.com/problemset/status/349/problem/A/page/1?order=BY_PROGRAM_LENGTH_ASC

看这个人 CXXXX

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 #include <stdlib.h>
 5 using namespace std;
 6 
 7 const int maxn = 1e5 + 5;
 8 int a[maxn], cnt[105];
 9 
10 int main()
11 {
12     int i, n, sum, flag, flag1;
13     while (scanf("%d", &n) != EOF)
14     {
15         for (i = 0; i < n; i++)
16         {
17             scanf("%d", &a[i]);
18         }
19         memset(cnt, 0, sizeof(cnt));
20         flag = flag1 = sum = 0;
21         for (i = 0; i < n; i++)
22         {
23             if (a[0] != 25)       // 第一张一定要是收到25，否则根本无法找零钱
24             {
25                 flag = 1;
26                 break;
27             }
28             else
29             {
30                 sum += a[i];        // 从一开始到当前所拥有的钱的总数
31             //    printf("sum = %d\n", sum);
32                 if (a[i] == 50)
33                 {
34                     cnt[50]++;   // 代表50面额的数量增加
35                     if (cnt[25] > 0)       // 要找25卢布，相应的25卢布这个面额的数量减少
36                     {
37                         cnt[25]--;
38                         sum -= 25;      // 当然总的钱数也需要减少
39             //            printf("50 cnt[25] = %d, cnt[50] = %d\n", cnt[25], cnt[50]);
40                     }
41                     else
42                         flag1 = 1;          // 无力找钱给人
43                 }
44                 else if (a[i] == 100)
45                 {
46                     cnt[100]++;
47                     if (cnt[50] > 0 && cnt[25] > 0)
48                     {
49                         cnt[50]--;       // 找1张50和一张25
50                         cnt[25]--;
51                         sum -= 75;
52                 //        printf("100: cnt[25] = %d, cnt[50] = %d, cnt[100] = %d\n", cnt[25], cnt[50], cnt[100]);
53                     }
54                     else if (cnt[25] > 2)
55                     {
56                         cnt[25] -= 3;    // 找3张25给人
57                         sum -= 75;
58                 //        printf("100: cnt[25] = %d\n", cnt[25]);
59                     }
60                     else
61                         flag1 = 1;
62                 }
63                 else if (a[i] == 25)
64                 {
65                     cnt[25]++;
66             //        printf("25: cnt[25] = %d\n", cnt[25]);
67                 }
68         //        printf("final sum = %d\n\n", sum);
69             }
70         }
71         if (flag)
72             printf("NO\n");
73         else if (flag1)
74             printf("NO\n");
75         else
76             printf("YES\n");
77     }
78     return 0;
79 }