本题解同步更新于我的博客 欢迎围观★,°:.☆(￣▽￣)/$:.°★ 。

题意描述

这一题的意思其实就是，让你构造一个$n\ast kn\; *\; k$的矩阵，使得第 i 列的总和为 i ，同时使得：每一列的任意两个数之间的差不大于1，且任意两行之间的总和差不大于1。

$1\le n\ast k\le 10^{6}1\; \backslash le\; n\; *\; k\; \backslash le\; 10^6$

观察样例：

输入：

5 5

输出：

 0 0 1 1 1
 0 0 1 1 1
 1 0 1 0 1
 0 1 0 1 1
 0 1 0 1 1

可以发现一个规律，可能这样不太好看出来，但是如果是这样就很清楚了。

 1 0 1 0 1
 0 1 0 1 1
 0 1 0 1 1
 0 0 1 1 1
 0 0 1 1 1

 1..1...
 ..1...
 ..1...
 ...1 ...
 ...1 ...

也就是每一列，从当前位置从上往下循环加一，当达到这一列的总数时，跳到下一列，而下一列的起始位置就是上一列加一。

但是，如果我们直接暴力模拟加的过程，肯定是会超时的，因为这样的时间复杂度是总共的个数$\frac{n(n+1)}{2}\backslash frac\{n\; (n\; +\; 1)\}\{2\}$，也就是$O(n^2)O(n^2)$的，这样显然会超时。

我们想对于第 i 列，循环去加，实际上每个数是加了$\lfloor \frac{i}{k}\rfloor \backslash lfloor\; \backslash frac\{i\}\{k\}\; \backslash rfloor$循环次，剩下不能凑成整循环的$i\mathrm{m}\mathrm{o}\mathrm{d}ki\; \backslash mod\; k$个，再加上 1 ，这样每个数的结果就可以直接算出，不需要模拟去加了。

时间复杂度$O(n\cdot k)O(n·k)$

为什么是对的

首先我们的构造是循环在第 i 列的每个位置加 1 ，因此也就是说每个数最大是$\lfloor \frac{i}{k}\rfloor +1\backslash lfloor\; \backslash frac\{i\}\{k\}\; \backslash rfloor\; +\; 1$，最小是$\lfloor \frac{i}{k}\rfloor \backslash lfloor\; \backslash frac\{i\}\{k\}\; \backslash rfloor$，相差最大为一，满足题目要求。

其次，我们将每次加的列数排开，例如样例：123451234512345..，发现我们同样可以用相同方法，设总数为 sum，那每一列最多为$\lfloor \frac{sum}{k}\rfloor +1\backslash lfloor\; \backslash frac\{sum\}\{k\}\; \backslash rfloor\; +\; 1$，最少为$\lfloor \frac{sum}{k}\rfloor \backslash lfloor\; \backslash frac\{sum\}\{k\}\; \backslash rfloor$，相差最 1 ，同样满足要求。

代码

#include<bits/stdc++.h>
using namespace std;

int n, k;

int main()
{
    scanf("%d%d", &n, &k);
    int m[k + 1][n + 1];
    for(int i = 1; i <= k; i++)
        for(int j = 1; j <= n; j++)
            m[i][j] = 0;
    int now = 1;
    for(int i = 1; i <= n; i++)
    {
        int tmp = i / k;
        for(int j = 1; j <= k; j++)
        {
            m[j][i] += tmp;
        }
        for(int j = 1; j <= i % k; j++)
        {
            m[now][i]++;
            now++;
            if(now > k)
                now = 1;
        }
    }
    for(int i = 1; i <= k; i++)
    {
        for(int j = 1; j <= n; j++)
            printf("%d ", m[i][j]);
        printf("\n");
    }
    
    return 0;
}