CF 349 C. Dominoes 贪心吧

2 3
01 11 00
00 01 11

11 11 10
00 00 01

4 1
11
10
01
00

11
10
01
00

因为关心的是每一列的和，使最大值最小化，我们只需要把01型(和10型是一样的)和11型填上去即可。

所以如果填写时填在某一列的任意一行效果都一样，那么为了方便处理，不妨尽量往上填写。

首先对于11型肯定是要处理的，不妨先处理11型，从上到下，从左到右，依次填下，

我们奇数行从左向右填，偶数行从右向左填，为什么呢，方便底下的一些处理。

11填完了，我们按照这个顺序填01和10，

假如上面一行出界了，随便填10或01

否则，假如上面一行是11，那么随便填10或01

否则，假如上面一行是10，填01

否则，假如上面一行是01，填10,

直到填完一个1的类型，结束。

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF =0x3f3f3f3f;
const int maxn=1000    ;

int a[maxn+5][maxn+5];
char s[2];
int n,m;
int num[4];//0表示两个是0,1表示左1右0,2表示左0右1,3表示11。
void get()
{
    if(s[0]=='0'&&s[1]=='0')
    {
        num[0]++;//全部是0，0类型加1
        return ;
    }
    else if(s[0]=='1'&&s[1]=='1')
    {
        num[3]++;//全部是1,1类型加1
        return ;
    }
    num[1]++;//否则记为1类型，因为1和2其实是一样的，因为可以倒着放。

}


bool in(int &y,int &x)
{
    return 1<=y&&y<=n&&1<=x&&x<=m;
}
void fill(int y,int x)
{
    if(num[1]==0&&num[3]==0)
   {
        a[y][x]=0;
        return;
    }

    if(num[3])
    {
        a[y][x]=3;
        num[3]--;
        return;
    }




    int ty=y-1,tx=x;
    if(!in(ty,tx))
    {
        a[y][x]= 1;
        num[1]--;
        return;
    }
    if(a[ty][tx]==1)
    {
        a[y][x]=2;
        num[1]--;
    }
    else
    {
        a[y][x]=1;
        num[1]--;
    }



}
void work()
{
    for(int i=1;i<=n;i++)
    {
        int j=i%2?1:m;
        int add=i%2?1:-1;
        
        for(  ; 1<=j&&j<=m ;j+=add)
        {
            fill(i,j);

        }

    }


}

void print()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(j!=1)  putchar(' ');
            if(a[i][j]==0)  printf("00");
            else if(a[i][j]==1) printf("10");
            else if(a[i][j]==2)  printf("01");
            else printf("11");
        }
        putchar('\n');
    }
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(num,0,sizeof num);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%s",s);
                get();
            }
        }
        work();
        print();


    }

   return 0;
}