【CF1627B】Not Sitting（模拟，贪心）

【题目描述】
Rahul和Tina在玩一个游戏。游戏在一个

    n
   
   
    ×
   
   
    m
   
  
  
   n\times m
  
 
n×m的网格图上进行，记第

 
  
   
    r
   
  
  
   r
  
 
r行第

 
  
   
    c
   
  
  
   c
  
 
c列上的格子为

 
  
   
    (
   
   
    r
   
   
    ,
   
   
    c
   
   
    )
   
  
  
   (r,c)
  
 
(r,c)。定义

 
  
   
    (
   
   
    a
   
   
    ,
   
   
    b
   
   
    )
   
  
  
   (a,b)
  
 
(a,b)与

 
  
   
    (
   
   
    c
   
   
    ,
   
   
    d
   
   
    )
   
  
  
   (c,d)
  
 
(c,d)之间的距离为

 
  
   
    
     ∣
    
    
     a
    
    
     −
    
    
     c
    
    
     ∣
    
   
   
    +
   
   
    
     ∣
    
    
     b
    
    
     −
    
    
     d
    
    
     ∣
    
   
  
  
   \left|a-c\right|+\left|b-d\right|
  
 
∣a−c∣+∣b−d∣。

游戏开始后，Tina会选择恰好

    k
   
  
  
   k
  
 
k个格子，并将其涂成粉红色。涂完以后，Rahul会选择任意一个没有被涂成粉红色的格子并在那个格子上坐下。此后，Tina也会选择任意一个格子（包括被涂成粉红色和没有被涂成粉红色的格子）并在那个格子上坐下。Rahul希望他和Tina之间的距离尽可能近，而Tina希望她和Rahul之间的距离尽可能远。于是，对于所有的

 
  
   
    k
   
   
    ∈
   
   
    [
   
   
    0
   
   
    ,
   
   
    n
   
   
    ×
   
   
    m
   
   
    −
   
   
    1
   
   
    ]
   
   
    ∩
   
   
    
     N
    
    
     ∗
    
   
  
  
   k\in[0,n\times m-1]\cap\N^*
  
 
k∈[0,n×m−1]∩N∗，Rahul都想知道他和Tina之间的距离是多少。

【输入格式】
输入包含多组测试样例，第一行一个整数

    t
   
  
  
   t
  
 
t表示测试样例数量。

对于每个测试样例，输入一行两个整数

    n
   
   
    ,
   
   
    m
   
  
  
   n,m
  
 
n,m。

数据保证

    n
   
   
    ×
   
   
    m
   
  
  
   n\times m
  
 
n×m之和不超过

 
  
   
    1
   
   
    
     0
    
    
     5
    
   
  
  
   10^5
  
 
105。

【输出格式】
对于每组测试样例输出一行

    n
   
   
    ×
   
   
    m
   
  
  
   n\times m
  
 
n×m个整数，依次表示当

 
  
   
    k
   
   
    =
   
   
    0
   
   
    ,
   
   
    1
   
   
    ,
   
   
    …
   
   
    ,
   
   
    n
   
   
    ×
   
   
    m
   
   
    −
   
   
    1
   
  
  
   k=0,1,\dots ,n\times m-1
  
 
k=0,1,…,n×m−1时Rahul和Tina之间的距离。

【数据范围】

    t
   
  
  
   t
  
 
t组数据，

 
  
   
    1
   
   
    ≤
   
   
    t
   
   
    ≤
   
   
    5
   
   
    ×
   
   
    1
   
   
    
     0
    
    
     4
    
   
  
  
   1\leq t\leq 5\times 10^4
  
 
1≤t≤5×104。


 
  
   
    2
   
   
    ≤
   
   
    n
   
   
    ×
   
   
    m
   
   
    ,
   
   
    ∑
   
   
    (
   
   
    n
   
   
    ×
   
   
    m
   
   
    )
   
   
    ≤
   
   
    1
   
   
    
     0
    
    
     5
    
   
  
  
   2\leq n\times m,\sum(n\times m)\leq 10^5
  
 
2≤n×m,∑(n×m)≤105。

【输入样例】

2
4 3
1 2

【输出样例】

3 3 4 4 4 4 4 4 5 5 5 5
1 1

【分析】

Rahul先选择位置，假设刚开始所有位置都未被涂色，那么Rahul一定会选择最靠近中间的某个位置；而Tina一定会选择四个墙角中离Rahul最远的一个位置。

对于每一个被涂色的格子，总是被涂色前Rahul的最佳选择，因为他们的选择都是明智的，也就是说我们可以将被涂色的格子作为Rahul的位置。

因为每个格子都会被涂色，所以每个格子都会作为Rahul的座位。

这样，问题就简化为了：求出每个位置距离四个角落的距离的最大值，然后将他们放到一个数组中，从小到大排序输出即可。

【代码】

#include<iostream>#include<cstring>#include<algorithm>usingnamespace std;constint N =100010;int res[N];int n, m, cnt;intmain(){int T;
    cin >> T;while(T--){
        cnt =0;
        cin >> n >> m;for(int i =1; i <= n; i++)for(int j =1; j <= m; j++)
                res[cnt++]=max(max(abs(1- i)+abs(1- j),abs(n - i)+abs(1- j)),max(abs(1- i)+abs(m - j),abs(n - i)+abs(m - j)));sort(res, res + cnt);for(int i =0; i < cnt; i++) cout << res[i]<<' ';
        cout << endl;}return0;}