SSY20240916提高组T1题解__贪心+大模拟

题面

题面描述

fe和xt在玩一个游戏, 在$n\times m$的网格图上进行. 定义$(a,b),(c,d)$见距离为$|a-c|+|b-d|$
现在游戏按照以下步骤进行:

1. xt选择$k$个格子
2. fe选择一个格子(不能选择步骤 $1$ 中选过的格子)
3. xt再选择一个格子

现在fe想让两人最后选的格子间距离最大, xt想让这个距离最小. 假设两人都按照最优方式选择, 询问对于$k=0,1,2,...,n\times m-1$, 最后的距离是多少

输入输出格式

输入两个整数$n,m$
输出$n\times m$个整数, 表示对于不同$k$的间距

样例输入

4 3

样例输出

3 3 4 4 4 4 4 4 5 5 5 5

数据范围

对于$100\%$的数据, $2\le n\times m\le 10^5$

---

题解

(没有循环, 只进行了这3个步骤)
我们先假设$k=0$
fe知道, 无论自己选哪一个格子, xt都会尽量选和它成对角线的另一个格子(如图)
(金黄色表示fe和xt选的不同情况的一对各点)

所以fe就要尽量选取靠近网格中间的格点, 以缩小和最远点的距离.

但是很明显xt也知道这件事, 所以当$k!=0$时, xt就会优先占据中间的格子
因此, 当中间的格子都被占据后, fe就会选择中间格子拓展出去一层的格子
易证得这种方式选出来的最大值最小

以此类推, 当这些格子也被全部占据后, fe就会选择继续向外拓展的格子(每次拓展之后最大距离都会$+1$)
所以有多少个和当前距离等价的格子, 就输出多少个距离(如下图)
xt会从中间向外拓展, 占据相同颜色的格子(先占红色, 然后黄色, 然后绿色…)
最后算一下每种颜色格子的数量(大模拟), 和它到最远角落的距离, 输出即可
(这细节让我挂了$80$分, 痛失榜二)

AC CODE

屎山代码

#include <bits/stdc++.h>
using namespace std;int n,m;int main(){cin >> n >> m;if(n>m){swap(n,m);}if(n==1||m==1){n=n*m;int mid=n/2;if(n%2==1){printf("%d ",mid);mid++;while(mid<=n-1){printf("%d %d ",mid,mid);mid++;}}else{while(mid<=n-1){printf("%d %d ",mid,mid);mid++;}}}else if(n==2||m==2){n=n*m;if(m%2==1){int mid=m/2;mid++;printf("%d %d ",mid,mid);mid++;while(mid<=m){printf("%d %d %d %d ",mid,mid,mid,mid);mid++;}}else{int mid=m/2+1;while(mid<=m){printf("%d %d %d %d ",mid,mid,mid,mid);mid++;}}}else{int nn=n%2;if(nn==0){nn=2;}int mm=m%2;if(mm==0){mm=2;}// printf("nn:%d mm:%d\n",nn,mm);int num=nn*mm;if(num==1){num=0;}int N=(n-nn)/2,M=(m-mm)/2;int val=n/2+m/2;for(int x=1;x<=nn*mm;x++){printf("%d ",val);}int cntn=1;int cntm=1;while(cntn*2+nn<=n){num+=4;for(int x=1;x<=num;x++){
//            	cout << num << "awd";printf("%d ",val+cntn);}cntn++;cntm++;// N++;}// cout << endl << cntn << ' ' << cntm << endl;
//        cout << endl;while(cntm*2+mm<=m){for(int x=1;x<=n*2;x++){printf("%d ",val+cntm);}cntm++;}// cout << endl << cntn << ' ' << cntm << endl;
//        cout << endl;while(N>=1){for(int x=1;x<=N*4;x++){printf("%d ",val+cntm);}cntm++;N--;}// cout << "END";}return 0;
}