3359. 更多奇怪的照片
摘要
Title: 3359. 更多奇怪的照片
Tag: 贪心
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
3359. 更多奇怪的照片
-
题意
Farmer John 正再一次尝试给他的 N 头奶牛拍照。
每头奶牛有一个范围在 1…100 之内的整数的「品种编号」，编号可能重复。
Farmer John 对他的照片有一个十分古怪的构思：他希望将所有的奶牛分为不相交的若干组（换句话说，将每头奶牛分到恰好一组中）并将这些组排成一行，使得第一组的奶牛的品种编号之和为偶数，第二组的编号之和为奇数，以此类推，奇偶交替。
Farmer John 可以分成的最大组数是多少？ -
思路
由于要求出最大组数，先将他们每个数字划分为一组，统计出奇数组和偶数组的初始数量
易得一个性质：每两个奇数组可以合并成一个偶数组
那么接下来的工作就简单了：每减少两个奇数组，增加一个偶数组，直到偶数组>=奇数组。这么做的原因是因为为了满足题意，要让偶数组和奇数组尽量多的同时，还要尽量相等 -
代码
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'''
Author: NEFU AB-IN
Date: 2022-05-22 20:59:08
FilePath: \ACM\Acwing\3359.1.py
LastEditTime: 2022-05-22 21:00:23
'''
n = int(input())
odd, even = 0, 0
a = list(map(int, input().split()))
for i in a:
if i & 1:
odd += 1
else:
even += 1
while odd > even:
odd -= 2
even += 1
if odd == even:
print(odd * 2) #如果奇数组最后数量和偶数组相同，那么最终的组数就是偶数组+奇数组
else:
print(odd * 2 + 1) #否则就是奇数组的数量小于偶数组的数量，那么最终除了每个偶数组和奇数组对应上，还会在末尾形成一个偶数组，即类似于 偶，奇，偶，奇，偶 这样的排列