CodeForces1138C.Skyscrapers

题目链接:CodeForces1138C.Skyscrapers

题意:

城市中有nm座高楼,可以从每座高楼向上下左右看见n+m-1座高楼,要求在每栋高楼观看,将高楼的高度从新标号,保证大小关系不变,问每个位置最少需要多少数字。

题解:

把每行每列抽出来,进行去重排序。然后对于每一点的建筑,二分查找其位置即可。

参考代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
vector<vector<int> > rows,cols,a;
void quchong(vector<int> &x)
{
    sort(x.begin(),x.end());
    auto it=std::unique(x.begin(),x.end());
    x.erase(it,x.end());
}
int main()
{
    scanf("%d%d",&n,&m);
    rows.resize(n,vector<int>(m));
    cols.resize(m,vector<int>(n));
    a=rows;
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    {
        scanf("%d",&a[i][j]);
        rows[i][j]=a[i][j];
        cols[j][i]=a[i][j];
    }
    for(int i=0;i<n;i++)
        quchong(rows[i]);
    for(int i=0;i<m;i++)
        quchong(cols[i]);
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    {
        auto &row=rows[i],&col=cols[j];
        int val=a[i][j];
        int r=lower_bound(row.begin(),row.end(),val)-row.begin();
        int c=lower_bound(col.begin(),col.end(),val)-col.begin();
        int x=row.size(),y=col.size();
        if(r>c)
            printf("%d ",max(x,r+y-c));
        else
            printf("%d ",max(y,c+x-r));
        if(j==m-1)
            puts("");
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。