Codeforces 816C/815A - Karen and Game

传送门：http://codeforces.com/contest/816/problem/C

本题是一个模拟问题。

有一个n×m的矩阵。最初，这个矩阵为零矩阵O。现有以下操作：

a.行操作“row i”：对第i(1≤i≤n)行的所有元素加一；

b.列操作“col j”：对第j(1≤j≤m)列的所有元素加一。

经过有限次操作，矩阵变为$G=(g_{i,j})_{m*n}$。

对于给定的矩阵G，试判断G是否可以由零矩阵O通过有限次的“行操作”和“列操作”生成？若可以，则求一个操作步数最小的方案；否则，返回-1。

考虑一个矩阵。假定其首先进行“行操作”，再进行“列操作”。设对第i行的操作次数为row[i]，对第j行的操作次数为col[j]，则有g[i][j]=row[i]+col[j]。如此，求解row[]和col[]数组即可。

假设零矩阵O经过“行操作”后变为矩阵T，再由矩阵T经过“列操作”变为矩阵G。则row[i]取矩阵G中第i行的最小元素，col[j]取矩阵G-T中第j行的最小元素。若零矩阵O可以通过row[]和col[]数组对应的操作变为矩阵G，则row[]和col[]数组对应的操作方案为最优操作方案；否则，可行的操作方案不存在。

row[]和col[]数组的求解在程序实现上可以通过逆向模拟的方法。

值得注意的是，对于一个给定行列数目的矩阵，若其行数不大于列数，则首先进行“行操作”，再进行“列操作”是最佳选择；否则，首先进行“列操作”，再进行“行操作”是最佳选择。

参考程序如下：

#include <stdio.h>

#include <stdlib.h>

#define SIZE 100

#define MAX_VAL 1000

int n, m, cnt = ;

int g[SIZE][SIZE];

int row[SIZE], col[SIZE];

void row_operate(void)

{

    for (int i = ; i < n; i++) {

        row[i] = MAX_VAL;

        for (int j = ; j < m; j++)

            if (g[i][j] < row[i]) row[i] = g[i][j];

        for (int j = ; j < m; j++)

            g[i][j] -= row[i];

        cnt += row[i];

    }

}

void col_operate(void)

{

    for (int j = ; j < m; j++) {

        col[j] = MAX_VAL;

        for (int i = ; i < n; i++)

            if (g[i][j] < col[j]) col[j] = g[i][j];

        for (int i = ; i < n; i++)

            g[i][j] -= col[j];

        cnt += col[j];

    }

}

int main(void)

{

    scanf("%d%d", &n, &m);

    for (int i = ; i < n; i++)

        for (int j = ; j < m; j++)

            scanf("%d", &g[i][j]);

    if (n <= m) {

        row_operate();

        col_operate();

    }

    else {

        col_operate();

        row_operate();

    }

    for (int i = ; i < n; i++)

        for (int j = ; j < m; j++)

            if (g[i][j]) {

                printf("-1\n");

                exit();

            }

    printf("%d\n", cnt);

    for (int i = ; i < n; i++)

        for (int k = ; k < row[i]; k++)

            printf("row %d\n", i + );

    for (int j = ; j < m; j++)

        for (int k = ; k < col[j]; k++)

            printf("col %d\n", j + );

    return ;

}

巴特西

Codeforces 816C/815A - Karen and Game

最新文章

热门文章