7-40 奥运排行榜 (25分)--sort()排序，结构体，前驱

  1 #include <iostream>
  2 #include <algorithm>
  3 using namespace std;
  4 struct node//定义国家结构体
  5 {
  6     int order;
  7     double gold, mdl, ppl;
  8     int rank[5];
  9 }con[300];
 10 //4个比较函数
 11 bool cmp1(node a, node b)
 12 {
 13     return a.gold > b.gold;
 14 }
 15 bool cmp2(node a, node b)
 16 {
 17     return a.mdl > b.mdl;
 18 }
 19 bool cmp3(node a, node b)
 20 {
 21     return a.gold / a.ppl > b.gold / b.ppl;
 22 }
 23 bool cmp4(node a, node b)
 24 {
 25     return a.mdl / a.ppl > b.mdl / b.ppl;
 26 }
 27 int main()
 28 {
 29     int N, M;
 30     cin >> N >> M;
 31     for (int i = 0; i < N; i++)
 32     {
 33         con[i].order = i;
 34         cin >> con[i].gold >> con[i].mdl >> con[i].ppl;
 35     }
 36     struct node con2[300];//将con拷贝一份到con2，con保持不动，用con2来排序
 37     for (int i = 0; i < N; i++)
 38     {
 39         con2[i].order = con[i].order;
 40         con2[i].gold = con[i].gold;
 41         con2[i].mdl = con[i].mdl;
 42         con2[i].ppl = con[i].ppl;
 43     }
 44     int cst[300];//存放要咨询的国家编号
 45     for (int i = 0; i < M; i++)
 46     {
 47         cin >> cst[i];
 48     }
 49     int front[300];//front存放前驱结点，用于处理并列名次的情况，相同名次的国家有相同“根节点”，它们的排名就是它们根节点的排名
 50     sort(con2, con2 + N, cmp1);
 51     for (int i = 0; i < N; i++) front[i] = i;//处理前需要将front初始化
 52     for (int i = 0; i < N; i++)
 53     {
 54         int k;//k为排名对应的下标，真实排名是k+1
 55         if (i == 0 || con2[i].gold != con2[i - 1].gold)k = i;//如果没有并列的情况，名次就是i+1
 56         else
 57         {
 58             front[i] = front[i - 1];
 59             k = i;
 60             while (k != front[k])//注意这里while循环用意是处理并列排名的情况
 61             {
 62                 k = front[k];
 63             }
 64             //while处理完后k的值是多个并列数据中排在最前面的那个的下标，即这一组并列数据的排名都是此时的k值再+1
 65         }
 66         con[con2[i].order].rank[1] = k + 1;
 67     }//以下都是类似的方法
 68     sort(con2, con2 + N, cmp2);
 69     for (int i = 0; i < N; i++) front[i] = i;
 70     for (int i = 0; i < N; i++)
 71     {
 72         int k;
 73         if (i == 0 || con2[i].mdl != con2[i - 1].mdl)k = i;
 74         else
 75         {
 76             front[i] = front[i - 1];
 77             k = i;
 78             while (k != front[k])
 79             {
 80                 k = front[k];
 81             }
 82         }
 83         con[con2[i].order].rank[2] = k + 1;
 84     }
 85     sort(con2, con2 + N, cmp3);
 86     for (int i = 0; i < N; i++) front[i] = i;
 87     for (int i = 0; i < N; i++)
 88     {
 89         int k;
 90         if (i == 0 || con2[i].gold / con2[i].ppl != con2[i - 1].gold / con2[i - 1].ppl)k = i;
 91         else
 92         {
 93             front[i] = front[i - 1];
 94             k = i;
 95             while (k != front[k])
 96             {
 97                 k = front[k];
 98             }
 99         }
100         con[con2[i].order].rank[3] = k + 1;
101     }
102     sort(con2, con2 + N, cmp4);
103     for (int i = 0; i < N; i++) front[i] = i;
104     for (int i = 0; i < N; i++)
105     {
106         int k;
107         if (i == 0 || con2[i].mdl / con2[i].ppl != con2[i - 1].mdl / con2[i - 1].ppl)k = i;
108         else
109         {
110             front[i] = front[i - 1];
111             k = i;
112             while (k != front[k])
113             {
114                 k = front[k];
115             }
116         }
117         con[con2[i].order].rank[4] = k + 1;
118     }
119 
120     for (int i = 0; i < M; i++)
121     {
122         int order = cst[i];//题目说当多个计算方式排名相同时，输出最小编号的方式，这里利用<和<=可实现这一目的。
123         if (con[order].rank[1] <= con[order].rank[2] && con[order].rank[1] <= con[order].rank[3] && con[order].rank[1] <= con[order].rank[4])
124             cout << con[order].rank[1] << ":1";
125         else if (con[order].rank[2] < con[order].rank[1] && con[order].rank[2] <= con[order].rank[3] && con[order].rank[2] <= con[order].rank[4])
126             cout << con[order].rank[2] << ":2";
127         else if (con[order].rank[3] < con[order].rank[1] && con[order].rank[3] < con[order].rank[2] && con[order].rank[3] <= con[order].rank[4])
128             cout << con[order].rank[3] << ":3";
129         else if (con[order].rank[4] < con[order].rank[1] && con[order].rank[4] < con[order].rank[2] && con[order].rank[4] < con[order].rank[3])
130             cout << con[order].rank[4] << ":4";
131         if (i != M - 1)cout << ' ';
132     }
133     return 0;
134 
135 }