Codeforces Round #609 (Div. 2) D. Domino for Young 二分图染色

给你n个柱体，让你用1x2的方块覆盖，问最多能够覆盖多少个方格。

思路：我们用类似于二分图染色的思想。把方块染成为黑白。

假设黑色块比白色块多。那么对于一个没有匹配的白块一定有一个没有匹配的黑块和其对应，而且一定能从这个没有匹配的白块开始找到一条增广路h-b-h-b-h到这个没有匹配的黑块，那么这个白块一定可以匹配成功。所有覆盖的块数就是min(黑块数， 白块数)。

#include <bits/stdc++.h>
#define LL long long
#define mid (l+r>>1)
using namespace std;

int main(){

    int n, x; scanf("%d", &n);
    LL ans=0, s1=0, s2=0;
    for(int i=1; i<=n; i++){
        scanf("%d", &x);
        s1+=x/2; s2+=x/2;
        if(x%2){
            if(i%2){
                s1++;
            }
            else{
                s2++;
            }
        }
    }
    cout<<min(s1, s2)<<endl;

    return 0;
}