差分 + 模拟，CF 815A - Karen and Game

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

815A - Karen and Game

二、解题报告

1、思路分析

一个经典的差分数组的模板题目：可以进行区间 + - 1，请问将数组变相等的最少操作次数？

做法是：等价为差分数组除了第一个数 全变0 的最小操作次数

那么到了本题，我们看成 把 g 全成 0 的逆操作，如何判断是否可行？

行操作不影响行差分数组的值（除了第一个）

列操作会对每一个行差分数组在该列的值的影响相同

因而得出结论：所有行差分数组的值都相同

对称的考虑：所有列差分数组的值都相同

我们判断其中一个就好，如果不满足，就输出-1

然后的问题是：如何操作？怎么操作，操作数更少？

我们计算 minrow[i] = min{g[i]}，mincol[j] = min{ g[i][j] }

先操作行：那么每行都得操作 minrow[i] 次，然后列再补齐

先操作列：那么每列都得操作 mincol[j] 次，然后行再补齐

我们比较下那个少就按照哪个来就行

2、复杂度

时间复杂度： O(NM)空间复杂度：O(NM)

3、代码详解

 ​

// #define LOCAL
using System;
using System.Collections;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Numerics;
using Template;

Solution s = new();
s.Solve();

namespace Template
{
    internal class Solution
    {
#if LOCAL
        private static readonly string FILEPATH = "in.txt";
        private readonly StreamReader sr = new(FILEPATH);
#else
        private readonly StreamReader sr = new(Console.OpenStandardInput());
#endif
        private T Read<T>()
            where T : struct, IConvertible
        {
            char c;
            dynamic res = default(T);
            dynamic sign = 1;
            while (!sr.EndOfStream && char.IsWhiteSpace((char)sr.Peek())) sr.Read();
            if (!sr.EndOfStream && (char)sr.Peek() == '-')
            {
                sr.Read();
                sign = -1;
            }
            while (!sr.EndOfStream && char.IsDigit((char)sr.Peek()))
            {
                c = (char)sr.Read();
                res = res * 10 + c - '0';
            }
            return res * sign;
        }
        private T[] ReadArray<T>(int n)
            where T : struct, IConvertible
        {
            T[] arr = new T[n];
            for (int i = 0; i < n; ++i) arr[i] = Read<T>();
            return arr;
        }

        public void Solve()
        {
            StringBuilder output = new();
            int T = 1;
            //T = Read<int>();

            while (T-- > 0)
            {
                int n = Read<int>(), m = Read<int>();

                int[][] g = new int[n][];

                for (int i = 0; i < n; ++ i)
                {
                    g[i] = ReadArray<int>(m);
                }

                int ans = 0;

                int[] minrow = new int[n];
                int[] mincol = new int[m];
                Array.Fill(minrow, int.MaxValue);
                Array.Fill(mincol, int.MaxValue);

                long sr = 0, sc = 0;

                for (int i = 0; i < n; ++i)
                {
                    for (int j = 0; j < m; ++j)
                    {
                        if (i > 0 && g[i][j] - g[i - 1][j] != g[i][0] - g[i - 1][0])
                        {
                            ans = -1;
                            break;
                        }

                        minrow[i] = Math.Min(minrow[i], g[i][j]);
                        mincol[j] = Math.Min(mincol[j], g[i][j]);
                    }

                    sr += minrow[i];
                }

                if (ans == -1)
                {
                    output.Append(ans).AppendLine();
                    continue;
                }

                for (int j = 0; j < m; ++ j)
                {
                    sr += g[0][j] - minrow[0];
                    sc += mincol[j];
                }

                for (int i = 0; i < n; ++ i)
                {
                    sc += g[i][0] - mincol[0];
                }

                if (sr < sc)
                {
                    output.Append(sr).AppendLine();
                    for (int i = 0; i < n; ++ i)
                    {
                        for (int j = 0; j < minrow[i]; ++ j)
                        {
                            output.Append($"row {i + 1}").AppendLine();
                        }
                    }

                    for (int j = 0; j < m; ++j)
                    {
                        for (int i = 0; i < g[0][j] - minrow[0]; ++i)
                        {
                            output.Append($"col {j + 1}").AppendLine();
                        }
                    }
                } else
                {
                    output.Append(sc).AppendLine();
                    for (int j = 0; j < m; ++j)
                    {
                        for (int i = 0; i < mincol[j]; ++i)
                        {
                            output.Append($"col {j + 1}").AppendLine();
                        }
                    }

                    for (int i = 0; i < n; ++i)
                    {
                        for (int j = 0; j < g[i][0] - mincol[0]; ++j)
                        {
                            output.Append($"row {i + 1}").AppendLine();
                        }
                    }
                }
            }

            Console.Write(output.ToString());
        }
    }
}