CF1137A/1138C Skyscrapers

排序+数据结构

将每一行（每一列）都排个序，并将原位置的在这一行（列）中的排行记录在一个数组里

注意，要将楼高度相同的元素看作一个元素

如 1 1 4 5 6 8 8，则排行是

1 1 2 3 4 5 5

处理好后，枚举每一个十字路口，

若当前的处在的行的排行大于列的排行，则当前这个元素之后的列中元素应以行的排行开始依次递增，

若当前的处在的行的排行小于列的排行，则当前这个元素之后的行中元素应以列的排行开始依次递增，

注意，若当前的处在的行的排行等于列的排行时，则要从如上两个方面同时考虑，取最大值。

#include <bits/stdc++.h>

using namespace std;

int n,m,a[1010][1010],hh[1010][1010],ll[1010][1010];

int mh[1500],ml[1500];

struct node

{

    int wh,num;

};

vector <node> h[1010],l[1010];

bool cmp(node a,node b)

{

    return a.num<b.num;//以高度降序排序

}

int main()

{

    scanf("%d%d",&n,&m);

    for (int i=1;i<=n;i++)

    {

        for (int j=1;j<=m;j++)

        {

            scanf("%d",&a[i][j]);

        }

    }

    for (int i=1;i<=n;i++)//处理行的情况

    {

        node t;

        for (int j=1;j<=m;j++)

        {

            t.num=a[i][j];

            t.wh=j;

            h[i].push_back(t);

        }

        sort(h[i].begin(),h[i].end(),cmp);

        int how=0;

        for (int j=0;j<m;j++)

        {

            if (j!=0)

            {

                if (h[i][j-1].num==h[i][j].num)

                  how++;//重复的有多少个

            }

            hh[i][h[i][j].wh]=j+1-how;//记录排行

        }

        mh[i]=m-how;//最大值

    }

    for (int j=1;j<=m;j++)//处理列的情况

    {

        node t;

        for (int i=1;i<=n;i++)

        {

            t.num=a[i][j];

            t.wh=i;

            l[j].push_back(t);

        }

        sort(l[j].begin(),l[j].end(),cmp);

        int how=0;

        for (int i=0;i<n;i++)

        {

            if (i!=0)

            {

                if (l[j][i-1].num==l[j][i].num)

                  how++;

            }

            ll[l[j][i].wh][j]=i+1-how;

        }

        ml[j]=n-how;

    }

    for (int i=1;i<=n;i++)

    {

        for (int j=1;j<=m;j++)

        {

            int cha;

            if (hh[i][j]==ll[i][j])//如上

            {

                int cha1;

                cha1=mh[i]-hh[i][j];

                cha=ml[j]-ll[i][j];

                printf("%d ",max(max(hh[i][j]+cha,mh[i]),max(ll[i][j]+cha1,ml[j])));

            }

            else

            if (hh[i][j]>ll[i][j])

            {

                cha=ml[j]-ll[i][j];

                printf("%d ",max(hh[i][j]+cha,mh[i]));

            }

            else

            if (hh[i][j]<ll[i][j])

            {

                cha=mh[i]-hh[i][j];

                printf("%d ",max(ll[i][j]+cha,ml[j]));

            }

        }

        printf("\n");

    }

}

巴特西

CF1137A/1138C Skyscrapers

最新文章

热门文章