【模拟题】Make it Manhattan

绝地灬酷狼 2022-06-09 03:47 108阅读 0赞

### Make it Manhattan ###

【题目描述】  
混乱的城市已经变得无法控制。大楼随处乱造，城市的布局也是一片混乱。市长决定要结束这种局面，兵器并且想建造一个漂亮的、有组织的城市。  
通过一些研究，他找到了使这个成为现实的理想的方法。受到纽约曼哈顿的启发，他希望所有的房子都造在矩形的格子里，用南北向的林荫道和东西向的街道隔开。这些林荫道和街道都有相同的间距。  
在现在这种状况，房子已经规划在矩形格子里面了。事实上，每幢房子都恰好完全覆盖住一个矩形格子。但是，所有的楼房随机地散落在城市里，不毁坏房屋来造路是不可能的。为了使得更多的市民开心，市长想要毁坏尽量少的房子。给你当前的房屋建造状况，最小破坏量是多少呢？

![这里写图片描述][SouthEast]

上图说明了这个问题。阴影方块是原先的楼房。如果道路间距为3，上面的粗线条就是规划的道路，被经过的那个楼房就要被拆除了。  
【输入】  
输入文件的第一行为两个整数D和N，用一个空格隔开，分别代表道路间距、城市中的楼房数，1 <= D <= 1000, 1 <= N <= 100000。  
以下N行，每行两个整数x和y，用一个空格隔开，代表房屋的位置。-10^9 <= x,y <= 10^9。  
【输出】  
输出文件只有一行一个整数，代表最少需要毁坏的房屋数。  
【样例输入】（对应上面的图）  
3 10  
1 0  
2 0  
3 0  
4 0  
1 2  
0 3  
1 5  
3 5  
4 2  
\-2 2  
【样例输出】  
1

不知道这个叫不叫离散化..  
由于x,y的范围很大，因此显然不能直接建图。  
因为要计算的是每d行每d列的房子数，因此可以给x,y模d，并统计每d行每d列的房子数。  
但这样会有一些在交叉点多算了一次，所以要记入这些点并减去。

#include<cstdio>
    #include<iostream>
    #include<vector>
    #include<cmath>
    #include<cstring>
    using namespace std;
    struct point{
        int x;
        int y;
    };
    int map[1001][1001];
    int hang[1001];
    int lie[1001];
    int n,d;
    int change(int x){
        if(x>=0) return x%d;
        if (x<0){
            int y = abs(x%d)+1;
            if (y==d) return 0;
            else return y;
        }
    }
    int main(){
        //freopen("manhattan.in","r",stdin);
        //freopen("manhattan.out","w",stdout);
        scanf("%d%d",&d,&n);
        memset(map,0,sizeof(map));
        for (int i = 1;i<=n;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            //int x = change(a);int y = change(b);
            a%=d;b%=d;if (a<0) a+=d;
            if (b<0)b+=d;
            hang[a]++;
            lie[b]++;
            map[a][b]++;
        }
        int mins =1<<30;
        for (int i =0;i<d;i++){
            for (int j=0;j<d;j++){
                if (mins>hang[i]+lie[j]-map[i][j])
                    mins = hang[i]+lie[j]-map[i][j];
            }
        }
        cout<<mins;
    }

[SouthEast]: /images/20220609/748a98f51ba8476494992fa12d9f387b.png