7-40 Classificação Olímpica (25 pontos)

7-40 Classificação Olímpica (25 pontos) Cada ano olímpico, vários meios de comunidade publicam uma classificação dos países, mas leitores atentos notam que as classificações de diferentes países são ligeiramente diferentes. Por exemplo, quando a China tem o maior número de medalhas de ouro, os meios de comunicação chineses publicam o "Ranking de Medalhas de Ouro"; enquanto os Estados Unidos têm o maior número total de medalhas, então os meios de comunicação americanos publicam o "Ranking de Medalhas Totais". Se países com menor população publicassem um "Ranking de Medalhas por Habitante", talvez os países africanos se tornassem os líderes... Agora, por favor, escreva um programa que calcule a classificação de cada país consultado da forma mais bené possível para ele.

Formato de Entrada:

A primeira linha de entrada fornece dois inteiros positivos N e M (≤ 224, pois existem 224 países e regiões no mundo), que são o número total de países e regiões participantes e o número de países consultados, respectivamente. Para simplificar, numeramos os países de 0 a N−1. Em seguida, há N linhas de entrada, onde a linha i fornece o número de medalhas de ouro, o número total de medalhas e a população do país com número i−1 (em milhões), todos números inteiros no intervalo [0,1000], separaods por espaços. A última linha fornece os números dos M países consultados, separados por espaços.

Formato de Saída:

Em uma única linha, imprima a saída no formato "classificação:método" para cada país consultado, na ordem em que aparecem. A classificação deve ser calculada da forma mais benéfica para o país; o número do método de cálculo é: ranking de medalhas de ouro = 1, ranking de medalhas totais = 2, ranking de medalhas de ouro per capita = 3, ranking de medalhas totais per capita = 4. Os resultados devem ser separados por espaços, sem espaços extras no final.

Se um país tiver a mesma classificação em diferentes métodos, deve-se usar o número do método de cálculo mais baixo.

Exemplo de Entrada:

4 4
51 100 1000
36 110 300
6 14 32
5 18 40
0 1 2 3

Exemplo de Saída:

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

Análise do problema: Utilizar ordenação por tabela e quicksort para classificar cada elemento e armazená-lo em um array de estruturas, observando que quando o número de medalhas de ouro é igual, a classificação do próximo país é a mesma do anterior. Nota: A função que eu mesmo escrevi para comparar classificações iguais não passou -- reclamação de um iniciante

<div><div>```
 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 #include <string.h>
 5 
 6 struct Nação {
 7     float metricas[4];
 8     int ordenacao[4];
 9 } paises[224];
10 int indice[224];
11 int posicao[224];
12 
13 void Trocar(int i, int j) {
14     int temp = indice[i];
15     indice[i] = indice[j];
16     indice[j] = temp;
17 }
18 
19 void InicializarIndice(int N) {
20     for (int i = 0; i < N; i++) {
21         indice[i] = i;
22         posicao[i] = 0;
23     }
24 }
25 
26 void OrdenacaoRapida(int inicio, int fim, int criterio) {
27     if (inicio >= fim - 1)
28         return;
29     int meio = (inicio + fim) / 2;
30     Trocar(inicio, meio);
31     int k = inicio + 1;
32     for (int j = inicio + 1; j < fim; j++) {
33         if (paises[indice[j]].metricas[criterio] > paises[indice[inicio]].metricas[criterio])
34             Trocar(k++, j);
35     }
36     Trocar(inicio, k - 1);
37     OrdenacaoRapida(inicio, k - 1, criterio);
38     OrdenacaoRapida(k, fim, criterio);
39 }
40 
41 void DeterminarPosicoes(int N, int criterio) {
42     for (int j = 0; j < N; j++) {
43         if (j > 0 && paises[indice[j]].metricas[criterio] == paises[indice[j - 1]].metricas[criterio])
44             paises[indice[j]].ordenacao[criterio] = paises[indice[j - 1]].ordenacao[criterio];
45         else
46             paises[indice[j]].ordenacao[criterio] = j;
47     }
48 }
49 
50 int main() {
51     int N, M;
52     scanf("%d%d", &N, &M);
53     float populacao;
54     
55     for (int i = 0; i < N; i++) {
56         scanf("%f%f%f", &paises[i].metricas[0], &paises[i].metricas[1], &populacao);
57         paises[i].metricas[2] = paises[i].metricas[0] / populacao;
58         paises[i].metricas[3] = paises[i].metricas[1] / populacao;
59     }
60     
61     for (int i = 0; i < 4; i++) {
62         InicializarIndice(N);
63         OrdenacaoRapida(0, N, i);
64         DeterminarPosicoes(N, i);
65     }
66     
67     int consulta;
68     for (int i = 0; i < M; i++) {
69         int melhorPosicao = 65535;
70         int melhorMetodo = 65535;
71         scanf("%d", &consulta);
72         
73         for (int j = 0; j < 4; j++) {
74             if (paises[consulta].ordenacao[j] < melhorPosicao) {
75                 melhorPosicao = paises[consulta].ordenacao[j];
76                 melhorMetodo = j;
77             } else if (paises[consulta].ordenacao[j] == melhorPosicao && j < melhorMetodo)
78                 melhorMetodo = j;
79         }
80         
81         if (i != M - 1)
82             printf("%d:%d ", melhorPosicao + 1, melhorMetodo + 1);
83         else
84             printf("%d:%d", melhorPosicao + 1, melhorMetodo + 1);
85     }
86     
87     return 0;
88 }

Visualizar Código