国际大学生程序设计竞赛例题_4.4矩阵

1,题意:矩阵b[i][j]统计当前i*j块不同元素的个数.
2,解决:动态计算不同元素出现的最小列数和每一列对应的元素种类数.
3,实现代码:

#include <algorithm>
#include <iostream>
using namespace std;

const int MAXN=1005;
int a[MAXN][MAXN];//输入矩阵
int b[MAXN][MAXN];//输出
int r[MAXN][MAXN];//元素a[i][j]所对应的次数
struct node
{
    int row;
    int col;
}p[MAXN*MAXN];//保存排在当前位置的元素坐标

bool cmp(node m,node n) //技巧:排序二维数组
{
    return a[m.row][m.col]<a[n.row][n.col];
}

int nc[MAXN*MAXN];//保存每个元素出现的最小列数
int numc[MAXN];//保存每一列不同元素的个数

int main()
{
    freopen("4.4.in","r",stdin);
    freopen("main.txt","w",stdout);
    int m,n;
    int k;
    int total;
    while(cin>>m>>n)
    {
        memset(numc,0,sizeof(numc));
        k=0;
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
            {
                cin>>a[i][j];
                p[k].row=i;
                p[k++].col=j;
            }
        sort(p,p+k,cmp);//得到元素排序的位置
        total=0;
        r[p[0].row][p[0].col]=total;
        for(int i=1;i<k;i++) //得到a中每个元素对应的次序号
        {
            if(a[p[i-1].row][p[i-1].col]!=a[p[i].row][p[i].col])
                total++;
            r[p[i].row][p[i].col]=total;
        }
        for(int i=0;i<=total;i++) nc[i]=n;//元素对应的最小列数
        for(int i=0;i<m;i++)
        {
            int sum=0;
            for(int j=0;j<n;j++)
            {
                if(j<nc[r[i][j]])
                {
                    numc[nc[r[i][j]]]--;//原来的列种类数减1
                    //注:总是从左到右,所以右边负的会被赋值
                    nc[r[i][j]]=j;
                    numc[j]++;//现在的加1
                }
                sum+=numc[j];
                b[i][j]=sum;
            }
        }
        for(int i=0;i<m;i++)
        {
            cout<<b[i][0];
            for(int j=1;j<n;j++)
                cout<<" "<<b[i][j];
            cout<<endl;
        }
    }
    return 0;
}