Codeforces Round #609 (Div. 2) D. Domino for Young

链接：

https://codeforces.com/contest/1269/problem/D

题意：

You are given a Young diagram.

Given diagram is a histogram with n columns of lengths a1,a2,…,an (a1≥a2≥…≥an≥1).

Young diagram for a=[3,2,2,2,1].
Your goal is to find the largest number of non-overlapping dominos that you can draw inside of this histogram, a domino is a 1×2 or 2×1 rectangle.

思路：

黑白染色，让整个图形变成黑白交错，这样选颜色较少的那个就可以了

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n, v[2];

int main()
{
    scanf("%lld", &n);
    v[0] = v[1] = 0;
    int a;
    for (int i = 1;i <= n;i++)
    {
        scanf("%d", &a);
        v[0] += a/2;
        v[1] += a/2;
        if (a&1)
            v[i%2]++;
    }
    printf("%lld
", min(v[0], v[1]));

    return 0;
}