Acwing/3359. 更多奇怪的照片

输入样例1：

7
1 3 5 7 9 11 13
1
2

输出样例1：

3
1

样例1解释

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

输入样例2：

7
11 2 17 13 1 15 3
1
2

输出样例2：

5
1

样例2解释

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

题解

见注释 贪心

#include 
#include 
#include 
#include 
#include 

using namespace std;

int main(){
	int n;
	cin>>n;
	int odd = 0, even = 0; // 分别存储奇偶数
	int temp;
	for(int i = 0; i < n; i++){
		cin>>temp;
		if(temp%2) odd++;
		else even++;
	}
	
	// 利用奇偶数的数量来贪心组合
	int ans;
	if(odd >= even){
		// 奇数比偶数多或相同
		// 首先一定有偶数*2组
		ans = even*2;
		// 剩余的奇数两个相加为偶数，一个做奇数组
		int odd_size = odd - even;
		ans += (odd_size / 3) * 2;
		// 还有单出来的一组，2个则是偶数组
		// 剩1个则只能回退将最后四个作为一组形成偶数，删除倒数第二个作为的奇数组
		if(odd_size%3 == 2) ans++; 
		else if(odd_size%3 == 1) ans--;
	} else {
		// 偶数比奇数多
		// 只能是多个偶数相加控制偶数组数比奇数多一组
		ans = odd*2 + 1;
	}
	cout<<ans<<endl;
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41