Even More Odd Photos

题目网址

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

分析：

前置知识：
奇 + 奇 = 偶
偶 + 偶 = 偶
奇 + 偶 = 奇
x & 1 = 1（x为奇数）

再来看这道题，让我们在约束条件下求出最大的分组，运用贪心的思想，这个问题转化成了，让每个组的数字个数最少的前提下，满足每组的奇偶性。

分类讨论：
1.当前组要求是奇数组，放一个奇数进去，如果没有停止判断。（此时只有两种情况：(1)只有偶数了，我们不用处理，可以视为把它放在前面的任意一偶数组。(2)没有数了，不用处理）
2.当前组要求是偶数组，放一个偶数进去，在没有时放两个奇数进去。（如果只有一个奇数，我们视为将它放在前面任意一个奇数组，变成偶数组后与另外任意一个偶数组合并，并将组数 - 1）

CODE：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll N = 1010; 
ll n,a[N],ji,ou,cnt = 1;
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n;for(int i = 1;i <= n;++i){ll x;cin >> x;//本题中具体数字我们并不关心，只要知道奇数偶数的个数就行了if(x & 1) ++ji;//jielse ++ou;}while(ji || ou){if(cnt & 1)//even{if(ou) --ou;else if(ji > 1) ji -= 2;else break;} else {if(ji) --ji;else break;}++cnt;//cout << ji << " " << ou << endl;}if(ji) --cnt;//特判cout << cnt - 1 << endl;//从1开始计数，要 - 1return 0;
}//1 ou,2 ji