codeforces 1269D. Domino for Young （二分图证明/结论题）

链接：https://codeforces.com/contest/1269/problem/D

题意：给一个不规则的网格，在上面放置多米诺骨牌，多米诺骨牌长度要么是1x2，要么是2x1大小，问最多放置多米诺骨牌的数量。

思路：首先这是一个结论题，对每个方格进行染色，一个方格染黑色，周围邻近的就染白色，答案就是黑色方格数量和白色方格数量的最小值。这个结论可以用二分图进行证明：把问题抽象成最大二分图匹配，每两个点之间连一条边。一个格子和周围格子连一条边，如果一个格子周围的还没被匹配，那么匹配数+1。如果一个格子周围已经全部被匹配完，那么该格子可以增广到任意一个为匹配位置，匹配数+1。所以只要在另一种颜色格子数量充沛的情况下，每一次匹配都能对匹配数贡献1，所以答案就是两种颜色的最小值。

AC代码：

#include<iostream>
#include<string>
#include<vector>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
const int maxn = 2e5+10;
struct node{
    int dif;
    int ti;
}g[maxn];
bool cmp(node a,node b){
    if(a.ti !=b.ti ) return a.ti<b.ti ;
    return a.dif <b.dif ; 
}
bool check(ll x){
    for(int i = 2;i<=sqrt(x);i++){
        if(x%i == 0) return true; 
    }
    return false;
}
int main(){
    ll black = 0 , white = 0;
    int n;cin>>n;
    int cur = 0;
    for(int i = 0;i<n;i++){
        ll a ;cin>>a;
        if(cur == 0){
            black +=(a/2+a%2);
            white +=a/2;
            cur = 1;
        }
        else{
            cur = 0;
            black +=a/2;
            white +=(a/2+a%2);
        }
    } 
    ll ans = min(black,white);
    cout<<ans;
    return 0;
}