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

 #include <iostream>

 #include <string.h>

 #include <stdio.h>

 #include <stdlib.h>

 using namespace std;

 const int maxn = 1e5 + ;

 int a[maxn], cnt[];

 int main()

 {

     int i, n, sum, flag, flag1;

     while (scanf("%d", &n) != EOF)

     {

         for (i = ; i < n; i++)

         {

             scanf("%d", &a[i]);

         }

         memset(cnt, , sizeof(cnt));

         flag = flag1 = sum = ;

         for (i = ; i < n; i++)

         {

             if (a[] != )       // 第一张一定要是收到25，否则根本无法找零钱

             {

                 flag = ;

                 break;

             }

             else

             {

                 sum += a[i];        // 从一开始到当前所拥有的钱的总数

             //    printf("sum = %d\n", sum);

                 if (a[i] == )

                 {

                     cnt[]++;   // 代表50面额的数量增加

                     if (cnt[] > )       // 要找25卢布，相应的25卢布这个面额的数量减少

                     {

                         cnt[]--;

                         sum -= ;      // 当然总的钱数也需要减少

             //            printf("50 cnt[25] = %d, cnt[50] = %d\n", cnt[25], cnt[50]);

                     }

                     else

                         flag1 = ;          // 无力找钱给人

                 }

                 else if (a[i] == )

                 {

                     cnt[]++;

                     if (cnt[] >  && cnt[] > )

                     {

                         cnt[]--;       // 找1张50和一张25

                         cnt[]--;

                         sum -= ;

                 //        printf("100: cnt[25] = %d, cnt[50] = %d, cnt[100] = %d\n", cnt[25], cnt[50], cnt[100]);

                     }

                     else if (cnt[] > )

                     {

                         cnt[] -= ;    // 找3张25给人

                         sum -= ;

                 //        printf("100: cnt[25] = %d\n", cnt[25]);

                     }

                     else

                         flag1 = ;

                 }

                 else if (a[i] == )

                 {

                     cnt[]++;

             //        printf("25: cnt[25] = %d\n", cnt[25]);

                 }

         //        printf("final sum = %d\n\n", sum);

             }

         }

         if (flag)

             printf("NO\n");

         else if (flag1)

             printf("NO\n");

         else

             printf("YES\n");

     }

     return ;

 }

巴特西

codeforces A. Cinema Line 解题报告

最新文章

热门文章