贪心算法在usaco铜组中一个难点，是考生需要掌握的算法之一。

下面，我们将讲解一道2021年一月的一道铜组题目。

[USACO21JAN] Even More Odd Photos B

题目描述

Farmer John 正再一次尝试给他的 N 头奶牛拍照（2≤N≤1000）。

每头奶牛有一个范围在 1 到 100 之内的整数的「品种编号」。Farmer John 对他的照片有一个十分古怪的构思：他希望将所有的奶牛分为不相交的若干组（换句话说，将每头奶牛分到恰好一组中）并将这些组排成一行，使得第一组的奶牛的品种编号之和为偶数，第二组的编号之和为奇数，以此类推，奇偶交替。

Farmer John 可以分成的最大组数是多少？

输入格式

输入的第一行包含 N。下一行包含 N 个空格分隔的整数，为 N 头奶牛的品种编号。

输出格式

输出 Farmer John 的照片中的最大组数。可以证明，至少存在一种符合要求的分组方案。

样例 #1

样例输入 #1

7
1 3 5 7 9 11 13

样例输出 #1

3

样例 #2

样例输入 #2

7

样例输出 #2

5

提示

样例解释 1

在这个样例中，以下是一种分成最大组数三组的方案。将 1 和 3 分在第一组，5、7 和 9 分在第二组，11 和 13 分在第三组。

样例解释 2

在这个样例中，以下是一种分成最大组数五组的方案。将 2 分在第一组，11 分在第二组，13 和 1 分在第三组，15 分在第四组，17 和 3 分在第五组。

题解

输出的答案为奇偶奇偶……排列，且易得数的大小对答案无影响。故先将输入的数分为奇偶两组，只需统计奇偶各自的数量即可。

我们须让组数尽可能得多，故若奇偶数都任然存在，应先选一个奇数和一个偶数配对，此时因为每次只消耗一个数，故分得组数最多。

当偶数或奇数一方耗尽（我们规定结尾的数为奇数）。此时，由于奇数和偶数性质不同，应当分类讨论。

1. 奇数耗尽（剩下全是偶数）：偶数无法排列出奇数，故剩下的偶数应当化为一个偶数。
2. 偶数耗尽（剩下全是奇数）：剩下的奇数可以组成奇数和偶数——奇数加奇数为偶数，一个奇数本身就是奇数。所以每三个奇数应当划为一组。

最后剩余的奇数有0、1、2三种情况。

1. 若剩余两个奇数，由于上一个结尾的数是奇数，最后两个奇数可以划为一个偶数看待，跟在前面的数后面。
2. 若最后不剩奇数，程序结束。、
3. 若最后剩余一个奇数，那么找寻规律可发现，最后几个数无论如何排列都不合法（偶奇奇、偶偶），故把最后四个数归为一个奇数，前面不受影响。

以上是一个比较粗略的解释，整个题目难度不小，这个题解不易理解。

以下为我的题解：

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin >> n;
	int odd = 0, even = 0;
	for (int i = 0; i < n; i++)
	{
		int c;
		cin >> c;
		if (c % 2 == 0)
			even++;
		else
			odd++;
	}
	if (even >= odd)
		cout << odd * 2 + (even > odd);
	else {
		int ans = even * 2;
		int extra = odd - even;
		if (extra % 3 == 0)
			ans += extra / 3 * 2;
		else if (extra % 3 == 2)
			ans += (extra - 2) / 3 * 2 + 1;
		else
			ans += (extra - 4) / 3 * 2 + (extra != 1);
		cout << ans;
	}
	return 0;
}

TAGS 编程 USACO 贪心算法