[Codeforces] CF1627B Not Sitting

题意

Rahul 和 Tina 在玩一个游戏。游戏在一个 \(n\times m\) 的网格图上进行，记第 \(r\) 行第 \(c\) 列上的格子为 \((r,c)\)。定义 \((a,b)\) 与 \((c,d)\) 之间的距离为 \(\left|a-c\right|+\left|b-d\right|\)。

游戏开始后，Tina 会选择恰好 \(k\) 个格子，并将其涂成粉红色。

涂完以后，Rahul 会选择任意一个没有被涂成粉红色的格子并在那个格子上坐下。

此后，Tina 也会选择任意一个格子（包括被涂成粉红色和没有被涂成粉红色的格子）并在那个格子上坐下。

Rahul 希望他和 Tina 之间的距离尽可能近，而 Tina 希望她和 Rahul 之间的距离尽可能远。

于是，对于所有的 \(k\in[0,n\times m-1]\cap\N^*\)，Rahul 都想知道他和 Tina 之间的距离是多少。

数据范围：

• \(t\) 组数据，\(1\leqslant t\leqslant 5\times 10^4\)。
• \(2\leqslant n\times m,\sum(n\times m)\leqslant 10^5\)。

思路

用excel啥的列个表格打个草稿就可以发现，不管Ruhul选在哪里，Tina的位置一定是在四个角中的一个

所以，只需要枚举\((x,y)\)，然后计算出其和四个角的最大值即可

因为随着变粉的格子越来越多，所以Ruhul离Tina的距离也一定越来越远，所以最后将每个格子的答案排序输出即可

代码

#include<bits/stdc++.h>
using namespace std;
int len(int a,int b,int c,int d)
{
	return abs(a-c)+abs(b-d);
}
void run()
{
	int n,m,x,y,cnt1,cnt2;
	vector<int>ans;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			int maxn=-1e9;
			maxn=max(maxn,len(i,j,1,1));
			maxn=max(maxn,len(i,j,1,m));
			maxn=max(maxn,len(i,j,n,1));
			maxn=max(maxn,len(i,j,n,m));
			ans.push_back(maxn);
//			cout<<maxn<<" ";
		}
//		cout<<"\n";
	}
	sort(ans.begin(),ans.end());
	for(int i=0;i<ans.size();i++) cout<<ans[i]<<" ";
	cout<<endl;
}
int main()
{
	int t;
	cin>>t;
	while(t--) run();
}