首页 > ACM题库 > HDU-杭电 > hdu 2584 Unversity Rankings-模拟[解题报告]C++
2014
02-10

hdu 2584 Unversity Rankings-模拟[解题报告]C++

Unversity Rankings

问题描述 :

At present, the university rankings are very popublar.They help senior high school students to choose universities for study.For example,you can find the CHINESE UNIVERSITY RANGKINGS at http://www.netbig.com/.
As we know ,a university ususally has many different departments,such as department of Language(FLS).some of them are quit good when comparing to other universities,but others are not.So,most of universities’rangkings are are composed of several ranking lists, each list for one department.
But here comes a problem that sometimes it’s hard to determine which universities is better,when comparing two universities with each othe.Fortunately,Doctor Bob has advanced a new concept named “absolutely better”,with which the problem above can be solved.
Now,here is a an example to explain the concept “absolutely better”:
Assum that there are three universities (X,Y,Z)and every university has three department:CS,EE and FLS.And the rangkings of the departments are as the followed:
The rankings of the CS:X>Y>Z(X>Y means X has a better CS department than Y)
The rankings of the EE:X>Z>Y
The rankings of the FLS:Z>X>y
Obviously,each each department of University X is better than that of University Y. Then,it’s called that X is absolutely better than Y.Using the “absolutely better”concept, it becomes better to compare some paires of Universities.
Now Bob has the complete rangkings of different departments of many universities,and he wants to find k universities(U1,u2,….Uk)such that Ui is absolutely better that Uj(for any i<j).

输入:

The first line of the input is a positive integer C.C is the number of test cases
followed.
The first line of each test case is two positive integers N,M(0<N,M<=100),N is the number of the universities and M is the number of departments.And then M lines follow.The i(th)(1<=i<=M)line contains N numbers Ui(1<=i<=N,1<=Ui<=N),indicating the ranking of the i(th)department.If Universitites Ui preceds to University Uj in line k(th department, then the k(th)department do Ui is better than k(th) department of Uj.

输出:

The first line of the input is a positive integer C.C is the number of test cases
followed.
The first line of each test case is two positive integers N,M(0<N,M<=100),N is the number of the universities and M is the number of departments.And then M lines follow.The i(th)(1<=i<=M)line contains N numbers Ui(1<=i<=N,1<=Ui<=N),indicating the ranking of the i(th)department.If Universitites Ui preceds to University Uj in line k(th department, then the k(th)department do Ui is better than k(th) department of Uj.

样例输入:

1
3 3
1 2 3
1 3 2 
3 1 2

样例输出:

2

#include<iostream>

using namespace std;

int rank[105][105];

int b[105];

int cmp(int *a,int *b,int n)

{

 int i;

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

   if(a[i]>b[i])

    break;

   if(i==n+1)

            return -1;

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

   if(a[i]<b[i])

    break;

   if(i==n+1)

            return 1;

   return 0;

}

int main()

{

    int c,i,j,max,temp,m,n;

    cin>>c;

    while(c--)

    {

     cin>>m>>n;//m university,n is department

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

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

      {

       scanf("%d",&temp);

       rank[temp][i]=j;

      }

      for(i=1;i<=m;i++)

      {

       max=i;

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

        if(cmp(rank[j],rank[max],n)==1)

         max=j;

        if(max!=i)

        {

         for(j=1;j<=n;j++)

         {

          temp=rank[max][j];

          rank[max][j]=rank[i][j];

          rank[i][j]=temp;

         }

        }

      }

     /* for(i=1;i<=m;i++)

      {

       for(j=1;j<=n;j++)

        cout<<rank[i][j]<<" ";

                 cout<<endl;

      }*/

      for(i=1;i<=m;i++)

       b[i]=1;

      for(i=1;i<=m;i++)

      {

       max=-1;

       for(j=1;j<i;j++)

       { 

        if(cmp(rank[i],rank[j],n)==-1)

        {

         //if(i==3)

        // cout<<max<<endl;

         if(b[j]>max)

          max=b[j];

        }

       }

        if(max+1>b[i])

         b[i]=max+1;//cout<<b[3]<<endl;

      }

      max=-1;

      for(i=1;i<=m;i++)

      {

       

       if(b[i]>max)

        max=b[i];

      }

      cout<<max<<endl;

    }

    return 0;

}

 


  1. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  3. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。