题解：CF1137A Skyscrapers

· · 题解

CF1137A 题目传送门

题目大意

给出一个 n \times m 的网格矩阵，网格中每个单元格都有一个权值 A_{i,j}。对于每一个单元格，提取这个单元格的行和列，允许对这一行和这一列上的每个单元格重新赋权值，但需要在保证矩阵中的这一行上元素之间和这一列上元素之间的相对大小均不改变的前提下，使得每个单元格权值的最大值最小，并记录下这个最小值，输出时，作为矩阵相应单元格的权值。每次操作每次按照输入格式，对应输出每一个单元格新的权值。

解决思路

概念理解

首先了解新概念离散化。

离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。

分别离散化每一行和每一列，然后使用二分得出每行和每列中分别有几个数比它大和比它小。在这一行一列中最多有 \max (xa, ya) 个比它小的数。最多有 \max (xb, yb) 个比它大的数。所以最后输出 \max (xa, ya) + \max (xb, yb)，并按题目输出格式换行即可。

代码展示

#include <iostream>
using namespace std;

const int N = 1010;
int n, m, x[N][N], a[N][N];
int b[N][N], va[N], vb[N], xa, ya;

int main()
{
    scanf("%d%d", &n, &m);//建议scanf,更快
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            scanf("%d", &x[i][j]);
            a[i][j] = x[i][j];//行离散化
            b[j][i] = x[i][j];//列离散化
        }
    for(int i = 1; i <= n; i++)
    {//离散化第 1 ~ n 行
        sort(a[i] + 1, a[i] + m + 1);//排序第i行
        va[i] = unique(a[i] + 1, a[i] + m + 1) - a[i] - 1;//va存储去重后的数组长度
        //unique函数可以对数组去重
    }
    for(int i = 1; i <= m; i++)
    {//离散化第 1 ~ m 列
        sort(b[i] + 1, b[i] + n + 1);//排序第i列
        vb[i] = unique(b[i] + 1, b[i] + n + 1) - b[i] - 1;//va存储去重后的数组长度
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            xa = lower_bound(a[i], a[i] + va[i], x[i][j]) - a[i];//二分查找x[i][j]在第i行从小到大排第几
            ya = lower_bound(b[j], b[j] + vb[j], x[i][j]) - b[j];//二分查找x[i][j]在第i列从小到大排第几 
            int xb = va[i] - xa, yb = vb[j] - ya;
            printf("%d ", max(xa, ya) + max(xb, yb));//建议printf,更快
        }
        printf("\n");//换行是个好习惯
    }
    return 0;
}