PTA 資料結構與算法 7-40 奧運排行榜

如有不對，不吝賜教

進入正題：

每年奧運會各大媒體都會公布一個排行榜，但是細心的讀者發現，不同國家的排行榜略有不同。比如中國金牌總數列第一的時候，中國媒體就公布“金牌榜”；而美國的獎牌總數第一，于是美國媒體就公布“獎牌榜”。如果人口少的國家公布一個“國民人均獎牌榜”，說不定非洲的國家會成為榜魁…… 現在就請你寫一個程式，對每個前來咨詢的國家按照對其最有利的方式計算它的排名。

輸入格式:

輸入的第一行給出兩個正整數N和M（≤224，因為世界上共有224個國家和地區），分别是參與排名的國家和地區的總個數、以及前來咨詢的國家的個數。為簡單起見，我們把國家從0 ~ N−1編号。之後有N行輸入，第i行給出編号為i−1的國家的金牌數、獎牌數、國民人口數（機關為百萬），數字均為[0,1000]區間内的整數，用空格分隔。最後面一行給出M個前來咨詢的國家的編号，用空格分隔。

輸出格式:

在一行裡順序輸出前來咨詢的國家的排名:計算方式編号。其排名按照對該國家最有利的方式計算；計算方式編号為：金牌榜=1，獎牌榜=2，國民人均金牌榜=3，國民人均獎牌榜=4。輸出間以空格分隔，輸出結尾不能有多餘空格。

若某國在不同排名方式下有相同名次，則輸出編号最小的計算方式。

輸入樣例:

4 4

51 100 1000

36 110 300

6 14 32

5 18 40

0 1 2 3

輸出樣例:

1:1 1:2 1:3 1:4

這道題目屬于結構體排序，隻要注意一下按照什麼方式來排序，以及注意浮點數的大小比較時不能直接應用’=='來比較，因為浮點數的存儲是不能完全用二進制來表示的（有時即便你在debug中的變量檢視時是一樣的，但是在小數點很多位後面可能會有不同），是以浮點數的比較應該是比較內插補點是否小于某個很小的數（我一般選取0.00001，不過這個看題目的精度就好了）。

下面給出代碼：

#include<stdio.h>
#include<math.h>

#define point 0.0001  //表示可接受的誤差（因為有浮點計算）

struct Country{
double data;       //該項資料
int number;          //國家編号
};

void QuickSort(struct Country *country,int left,int right);

int main(void)
{
    int N,M,i,j;
    fscanf(stdin,"%d %d",&N,&M);
    struct Country country[4][N];     //4種排名 N個國家
    int query[M];        //0:金牌榜 1:獎牌榜 2：人均金牌 3：人均 獎牌
    int rank[4][N];      //國家的排名

    for(i=0;i<N;i++){
      int people;
      fscanf(stdin,"%lf %lf %d",&country[0][i].data,&country[1][i].data,&people);
      country[2][i].data=country[0][i].data/people;
      country[3][i].data=country[1][i].data/people;     //初始化獎牌數目
      for(j=0;j<4;j++)
        country[j][i].number=i;         //初始化國家的編号
    }

    for(i=0;i<4;i++){
      QuickSort(*(country+i),0,N-1);    //分段排序 排完序之後資料按降序
      rank[i][country[i][0].number]=1;
      int delta=1;
      for(j=1;j<N;j++){
        rank[i][country[i][j].number]=rank[i][country[i][j-1].number];    //為第j個國家的第i種排名
        if(fabs(country[i][j].data-country[i][j-1].data)>point){
          rank[i][country[i][j].number]+=delta;
          delta=1;
        }
        else
          delta++;
      }
    }

    for(i=0;i<M;i++)
      fscanf(stdin,"%d",query+i);

    for(i=0;i<M;){
      int temp=rank[0][query[i]];
      int index=0;
      for(j=1;j<4;j++)
        if(rank[j][query[i]]<temp){
          index=j;
          temp=rank[j][query[i]];
        }
      printf("%d:%d",temp,index+1);
      if(++i!=M)
        putchar(' ');
    }

    return 0;
}

void QuickSort(struct Country *country,int left,int right)
{
    if(left>=right)
      return ;

    int i,j;
    struct Country temp;

    i=left;
    j=right;

    while(i!=j){
      while(i!=j&&country[j].data<=country[left].data)
        j--;
      while(i!=j&&country[i].data>=country[left].data)
        i++;
      if(i!=j){
        temp=country[i];
        country[i]=country[j];
        country[j]=temp;
      }
    }

    if(i!=left){
      temp=country[i];
      country[i]=country[left];
      country[left]=temp;
    }

    QuickSort(country,left,i-1);
    QuickSort(country,i+1,right);

    return ;
}

           

測試結果：