ouuan 的博客

ouuan 的博客

题解 CF1173B 【Nauuo and Chess】

posted on 2019-06-08 13:47:53 | under 题解 |
  1. $m\ge\left\lfloor\frac n 2\right\rfloor+1$

    $\because\begin{cases}|r_1-r_n|+|c_1-c_n|\ge n-1\\|r_1-r_n|\le m-1\\|c_1-c_n|\le m-1\end{cases}$

    $\therefore m-1+m-1\ge n-1$

    $\therefore m\ge\frac{n+1}2$

    $\because m\text{是整数}$

    $\therefore m\ge\left\lfloor\frac n 2\right\rfloor+1$

  2. $m$ 可以取到 $\left\lfloor\frac n 2\right\rfloor+1$

    在每一斜行放一颗棋子即可,即: $r_i+c_i=i+1$ 。因为 $|r_i-r_j|+|c_i-c_j|\ge|r_i+c_i-r_j-c_j|$ 。

#include <cstdio>

using namespace std;

int main()
{
    int n, i, ans;

    scanf("%d", &n);
    ans = n / 2 + 1;

    printf("%d", ans);

    for (i = 1; i <= ans; ++i) printf("\n%d 1", i);
    for (i = 2; i <= n - ans + 1; ++i) printf("\n%d %d", ans, i);

    return 0;
}