Solução por Rogério Júnior
Este é um modelo bem simples de um problema de ordenação. No C++, quase sempre usaremos uma função da biblioteca $$algorithm$$ chamada $$sort$$ para ordenarmos um vetor. Se você não a conhece, clique aqui. Resumindo, ela tem três parâmetros: o primeiro é um ponteiro para a primeira posição do vetor a ser ordenada, a segunda um ponteiro para a primeira posição do vetor que não será ordenada e a terceira a função de ordenação que usaremos. Se deixarmos o último parâmetro em branco, ela ordenará usando os operadores “<” e “>”. Para salvar cada time, usaremos um vector de string de nome Time (para não confundir com a função time, do C), usando portanto uma vetor de vector para representar todos os times. Se você não conhece a string, clique aqui, e se não conhece o vector, clique aqui.
A primeira coisa a fazermos é salvarmos todos os alunos. Para isso, usaremos dois vetores, o string nome[MAXN] e o int hab[MAXN]. Cada aluno será identificado por seu índice na entrada (o primeiro aluno é o 1, o segundo é o 2 e assim por diante) e, em $$nome[i]$$ estará salvo o nome do aluno i, cuja habilidade estará salva em $$hab[i]$$. Depois, iremos declarar um vetor de N números, e iremos preenchê-lo com os números de 1 a N. Este vetor representará a ordem dos alunos por habilidade. Para que isso ocorra, chamaremos o sort. Se chamarmos este vetor de $$ordem$$ e o indexarmos de 1 a N, o ponteiro para seu começo será $$ordem+1$$ e para o seu final será $$ordem+N+1$$. O terceiro parâmetro será a função de comparação, que chamaremos de $$compara$$. Precisamos criá-la. A $$compara$$ receberá dois inteiros e retornará uma bool, true se os dois inteiros estiverem ordenados seguindo a ordem que criamos e false caso contrário. Em outras palavras, se a função receber como parâmetros (int x, int y), será true se $$hab[x]>hab[y]$$ e false caso contrário.
Feito isso, teremos os índices dos alunos no vetor $$ordem$$ totalmente ordenados por habilidade. Agora vamos criar a o vetor de vector de string $$Time$$. Vamos percorrer o $$ordem$$ casa por casa adicionando o nome de cada elemento em um dos vector‘s de $$Time$$. Para fazer isso, faremos um for que percorrerá todo o vetor $$ordem$$ e usará o resto da posição no módulo T (quantidade de times) para saber em que time tal jogador deve entrar. Para inserir um elemento em um vector usamos a função push_back, do próprio vector, que recebe como parâmetro o elemento a ser inserido no seu final. Feito isso, teremos T vector‘s e cada um será um time. Agora basta ordená-los com um sort (não precisamos criar função de comparação pois a string já tem os operadores “<” e “>”) e imprimir cada um de seus elementos, antecedidos pelo índice do time. Para ordená-los, vale lembrar que, no vector, o ponteiro para o começo é a função begin() e para o fim é a função end(), ambas do próprio vector.
Basta agora notar dois detalhes importantes. Como, no começo e no fim do código, irei ler e imprimir uma string? Para imprimir é fácil, uso o printf como se fosse imprimir uma string do C (vetor de char) e chamo a função c_str(), da string, que converte uma string em string de C. Para imprimir uma string de nome $$frase$$, por exemplo, uso o comando “printf(“%s”, frase.c_str());“. Para ler, não podemos usar essa função. Nós usamos um vetor de char $$auxiliar$$, lemos a entrada e a salvamos nele e depois fazemos a string receber o valor de $$auxiliar$$. Segue o código:
| #include <cstdio> // scanf e printf | |
| #include <string> // string | |
| #include <vector> // vector | |
| #include <algorithm> // sort | |
| #define MAXN 10100 // limite de n | |
| #define MAXT 1010 // limite de t | |
| using namespace std; | |
| //declarção de variáveis | |
| int n, t, hab[MAXN], ordem[MAXN]; | |
| string nome[MAXN]; | |
| vector<string> Time[MAXT]; | |
| char auxiliar[110]; | |
| bool compara(int x, int y){ // função de comparação do sort | |
| // o parâmetro x vem antes do parâmetro y, logo | |
| if(hab[x]>hab[y]) return true; // se a habilidade de x for maior, x e y estão ordenados | |
| return false; // caso contrário, não estão | |
| } | |
| int main(){ | |
| scanf("%d %d", &n, &t); // leio os valores de n e t | |
| for(int i=1; i<=n; i++){ // para cada aluno da entrada | |
| scanf(" %s %d", auxiliar, &hab[i]); // leio seu nome e sua habilidade | |
| nome[i]=auxiliar; // salvo o nome no vetor nome, como string | |
| } | |
| for(int i=1; i<=n; i++) ordem[i]=i; // preencho o vetor ordem com os números de 1 a n | |
| sort(ordem+1, ordem+n+1, compara); // ordeno o vetor com a função compara | |
| for(int i=1; i<=n; i++){ // para cada posição do vetor ordem | |
| int aluno=ordem[i]; // vejo o aluno que está salvo na posição | |
| int davez=i%t; // vejo o time em que ele deve ficar | |
| if(davez==0) davez=t; // se i for múltiplo de t, deve ficar no time t, não no time 0 (que não existe) | |
| Time[davez].push_back(nome[aluno]); // e coloco o nome do aluno no referido time | |
| } | |
| for(int i=1; i<=t; i++){ // para cada time | |
| sort(Time[i].begin(), Time[i].end()); // ordeno seus alunos em ordem alfabética | |
| printf("Time %d\n", i); // imprimo o número do time | |
| for(int j=0; j<Time[i].size(); j++) printf("%s\n", Time[i][j].c_str()); // e imprimo o nome de um aluno em cada liha | |
| printf("\n"); // ao final, imprimo uma quebra de linha | |
| } | |
| return 0; | |
| } |
Nosso leitor Roger Benet também apresentou uma solução correta em java:
| import java.io.*; | |
| import java.util.Arrays; | |
| public class solucao { | |
| public static void main(String[] args) throws IOException { | |
| BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); | |
| BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); | |
| int num,qtd,i,j,x,y; | |
| String[] aux; | |
| aux = in.readLine().split(" "); | |
| num = Integer.parseInt(aux[0]); | |
| qtd = Integer.parseInt(aux[1]); | |
| String[] n = new String[num]; | |
| String[] t = new String[qtd]; | |
| int[] h = new int[num]; | |
| for(i = 0; i < qtd; i++)t[i] = ""; | |
| for(i = 0; i < num; i++){ | |
| aux = in.readLine().split(" "); | |
| n[i] = aux[0]; | |
| h[i] = Integer.parseInt(aux[1]); | |
| } | |
| for(i = 0; i < num – 1; i++){ | |
| for(j = i+1; j < num; j++){ | |
| if(h[i] > h[j]){ | |
| x = h[i]; | |
| h[i] = h[j]; | |
| h[j] = x; | |
| aux[0] = n[i]; | |
| n[i] = n[j]; | |
| n[j] = aux[0]; | |
| } | |
| } | |
| } | |
| j = 0; | |
| for(i = num – 1; i > -1; i–){ | |
| t[j] += n[i] + " "; | |
| j++; | |
| if(j == qtd)j = 0; | |
| } | |
| for(i = 0; i < qtd; i++){ | |
| out.write("Time "+(i+1)+"\n"); | |
| y = 0; | |
| x = 0; | |
| for(j = 0; j < t[i].length(); j++){ | |
| if(t[i].charAt(j) == ' '){ | |
| n[y] = t[i].substring(x,j); | |
| y++; | |
| x = j+1; | |
| } | |
| } | |
| Arrays.sort(n,0,y); | |
| for(j = 0; j < y; j++){ | |
| out.write(n[j]+"\n"); | |
| } | |
| out.write("\n"); | |
| } | |
| out.flush(); | |
| } | |
| } |

Comente