题解：P9941 [USACO21JAN] Even More Odd Photos B

44i11 · 2024-10-05 13:25:40 · 题解

P9941题解

题目传送门

看到题解区里没有和我一样的做法，就来写这篇题解了。

前置芝士

众所周知：

奇数+奇数=偶数

奇数+偶数=奇数

偶数+偶数=偶数

题意分析

有 n 个整数，让你将分为尽可能多的组，使得每一组的和奇偶交替。

解题思路

我们设 x 为组数，因为要求每一组的和奇偶交替，而偶数无法单独合成奇数，所以奇数的个数要大于等于 \frac{x}{2}，然后我们可以把一个偶数看成两个奇数(原因在前置芝士)，那么我们只要判断 是否有 \lceil \frac{x}{2} \rceil \times 2 + \frac{x}{2} 个奇数就可以了，最后要注意一个数加上偶数，这个数的奇偶性不变。所以，我们可以偶数个奇数分到任意组。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e3 + 5;
ll n, a[N], js, os; 
bool check(ll x){
    ll ans = os * 2 + js - (ll)ceil(x / 2.0) * 2 - x / 2;
    return ans >= 0 && ans % 2 == 0 && js >= x / 2;//思路同上
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }   
    for(int i = 1; i <= n; i++){//统计奇数和偶数
        if(!(a[i] % 2)){
            os++;
        }else{
            js++;
        }
    }
    for(int i = n; i >= 1; i--){
        if(check(i)){//判断分成i组是否可以
            cout << i;
            break;
        }
    }
    return 0;
}