Domino for Young题解

Wings_of_liberty · 2022-08-05 15:52:38 · 题解

分析

这道题是一道小学奥数类的题，首先，对于一个有 n 个格子的图，我们理论上来说能填上 \left\lfloor\dfrac{n}{2}\right\rfloor 个数，但是由于骨牌需要占两个相邻的格子，所以并不能达到这个数。

方法

我们将任意一个格子填上黑色，并将相邻的格子填上白色，以此类推，得到一个黑白相间的格子图，并且同色不相邻，由于放置一个骨牌需要两个相邻的格子，其实就是一个黑色格子加上一个相邻的白色格子，所以说，最后找到较少的格子的数量就可以。

注意

虽然说方法上是要把每一个格子涂上颜色，但是数据范围是 3\times10^5\times3\times10^5 如果开一个这么大的数组空间会超，然后考虑只记录一行。最后发现，如果奇数列最下方的格子上填的是白色，那么偶数列最下面一个一定填的是黑色，如果一列有偶数个格子，那么黑色白色各占一半，如果是奇数个格子，那么最下面格子是什么色，这个色就会比另一个颜色对占一个格子

代码实现

#include <bits/stdc++.h>
using namespace std;
int n;
int m;
long long bla=0,whi=0; 
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&m);
        long long w,b;
        if(m&1){
            w=m>>1,b=(m>>1)+1;
        }else{
            w=b=(m>>1);
        }
        if(i&1){//奇数行偶数行要交换一下最底下一格的颜色 
            whi+=w,bla+=b;
        }else{
            whi+=b,bla+=w;
        }
    }
    printf("%lld",min(whi,bla));
    return 0;
}