题目翻译:

有 $n \times n$ 大小的棋盘,一共放 $k$ 辆车,使得这个棋盘稳定。

稳定的概念是:所有的车移动至相邻四格(上下左右)不会出现一行一列有 $\ge 2$ 辆车。

做题思路:

我们可以考虑,移动之后没有同一行一列有多辆车,那么就让它移动之后还是只有它一辆车,换句话说,每辆车之间至少空一行和一列,也就是在对角线上放是最优想法。如果对角线放不下 $k$ 辆车了,无解输出 -1

深入思考(此分析大佬跳过)

在怎样的情况下 $n \times n$ 的棋盘放不下 $k$ 辆车呢?

很显然,每两行两列放一辆车,那么最多可以放 $\left\lfloor\dfrac{n+1}{2}\right\rfloor$ 辆车(大多数语言整数除法自动下取整),所以只要判断 $\dfrac{n+1}{2}$ 与 $k$ 的大小关系。

AC代码

void solve()
{
    int n,k;
    cin>>n>>k;
    if((n+1)/2<k)//判断是否放得下
    {
        cout<<-1<<endl;
        return;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j&&i%2!=0&&k>0)//判断分别为:对角线、隔一行一列、还可以放车
            {
                cout<<'R';
                k--;//放完一辆
            }
            else
            {
                cout<<'.';
            }
        }
        cout<<endl;
    }
}

多组数据,代码未全。请勿copy,当心踩坑!

最后修改:2023 年 04 月 22 日
v我50吃疯狂星期四