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;
}