codeforces A. Kitahara Haruki's Gift 解题报告

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

题目意思：给定 n 个只由100和200组成的数，问能不能分成均等的两份。

题目其实不难，要考虑清楚数量问题即可。就是说，200的数量是奇数或偶数，100的数量是奇数或偶数时的处理。

一开始可能思路有点混乱，学人3分钟打一道题，wa了3次。

由于写得比较混乱，我的代码不好意思贴出来，以下借鉴了别人的两种好的写法。

Time: 31ms Memory: 0KB

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 using namespace std;

 int main()

 {

     int n;

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

     {

         int tmp, c1, c2;

         c1 = c2 = ;

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

         {

             scanf("%d", &tmp);

             if (tmp == )

                 c1++;   // c1: 100的数量

             else

                 c2++;    // c2: 200的数量

         }

         c2 %= ;    // c2: 0 or 1

         c1 -= c2 * ;  // 一张c2 = 二张c1

         if (c1 <  || c1 & )  // c1不是偶数张（不能均分）或者c1只有0张，但c2是奇数张

             printf("NO\n");

         else

             printf("YES\n");

     }

 }

以下这个方法更加直接，不过一定要先排序，还有就是先从200的数量开始分配。

好厉害的写法！！！

Time：15ms Memory: 0KB

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 int a[maxn];

 int main()

 {

     int n, tmp;

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

     {

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

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

         sort(a, a+n);

         int fir = , sec = ;  // fir：第一个人分到的apple grams  sec：第二个人分到的

         for (int i = n-; i >= ; i--)

         {

             if (fir < sec)

                 fir += a[i];

             else

                 sec += a[i];

         }

         printf("%s\n", fir == sec ? "YES" : "NO");

     }

     return ;

 }

巴特西

codeforces A. Kitahara Haruki's Gift 解题报告

最新文章

热门文章