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

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int n;
 9     while (scanf("%d", &n) != EOF)
10     {
11         int tmp, c1, c2;
12         c1 = c2 = 0;
13         for (int i = 0; i < n; i++)
14         {
15             scanf("%d", &tmp);
16             if (tmp == 100)
17                 c1++;   // c1: 100的数量
18             else
19                 c2++;    // c2: 200的数量
20         }
21         c2 %= 2;    // c2: 0 or 1
22         c1 -= c2 * 2;  // 一张c2 = 二张c1
23         if (c1 < 0 || c1 & 1)  // c1不是偶数张（不能均分）或者c1只有0张，但c2是奇数张
24             printf("NO
");
25         else
26             printf("YES
");
27     }
28 }

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

好厉害的写法！！！

Time：15ms Memory: 0KB

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int maxn = 100 + 5;
 8 int a[maxn];
 9 
10 int main()
11 {
12     int n, tmp;
13     while (scanf("%d", &n) != EOF)
14     {
15         for (int i = 0; i < n; i++)
16             scanf("%d", &a[i]);
17         sort(a, a+n);
18         int fir = 0, sec = 0;  // fir：第一个人分到的apple grams  sec：第二个人分到的
19         for (int i = n-1; i >= 0; i--)
20         {
21             if (fir < sec)
22                 fir += a[i];
23             else
24                 sec += a[i];
25         }
26         printf("%s
", fir == sec ? "YES" : "NO");
27     }
28     return 0;
29 }

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

相关推荐