自动搬运

查看原文

来自洛谷，原作者为

	Milmon HN 高一最菜 OIer | 史上最菜的菜鸡 qaq | 快乐学习，认真刷题，努力进步！

搬运于2025-08-24 23:03:33，当前版本为作者最后更新于2024-05-07 21:53:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

当 $k \leq \min(m,n)$ 时，只需把 $k$ 个石头放在不同的行和列（例如放在对角线的前 $k$ 个位置），这样至少需要 $k$ 次宇宙射线才可以全部销毁，显然是最优的。

当 $k > \min(m,n)$ 时，由于不管怎么样都可以通过至多 $\min(m,n)$ 步全部销毁（直接对每行或每列依次销毁即可），所以可以先按照对角线放，多余石头随意摆放即可达到 $\min(m,n)$ 步。

有兴趣的读者可以思考一下 checker 的实现。

特别注意：不要每组数据都把整个数组 memset，否则会 TLE！

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

char mp[2000][2001];

int main(){
    int T; scanf("%d",&T);
    while(T--){
        int n,m,k;
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++)mp[i][j]='.';
            mp[i][m]='\0';
        }
        for(int i=0;i<min({n,m,k});i++)mp[i][i]='S';
        int i=0,j=0; k-=min({n,m,k});
        while(k){
            if(mp[i][j]=='.')mp[i][j]='S',k--;
            j++;
            if(j==m)i++,j=0;
        }
        for(int i=0;i<n;i++)
            printf("%s\n",mp[i]);
    }
    return 0;
}