PKU 2062 - Card Game Cheater

Autor da análise: schultzschultz

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2062

Resumo

Dados dois vetores de números inteiros A e B de mesmo tamanho, reordená-los de forma a maximizar o número de elementos em A maiores que seus pares em B.

Solução

Ordene A e B e execute o seguinte algoritmo:

c = 0; /* nao conseguimos ninguem */
i = 0; /* comecamos analisando o 1o elemento de cada vetor */
j = 0;
while (i != n) { /* enquanto ainda faltarem elementos para associar */
        if (A[i] > B[j]) {
                ++i; ++j; /* associe i com j */
                ++c; /* mais uma associacao feita */
                /* 
                 * observar que nao faz sentido associar ninguem maior que i a j
                 * por que A[i] eh o menor valor nao ocupado associavel a B[j].
                 */
        }
        else
                ++i; /* i não poderah ser associado a nenhum j a partir daqui */
}
 
print(c);

A prova de que esse algoritmo está correto é simples e pode ser obtida sem dificuldade a partir dos comentários no código acima. É bom fazê-la formalmente no papel para não ser enganado pela gulodice desse algoritmo.

Se você não se importar em matar uma mosca com um canhão, você pode fazer esse problema por emparelhamento máximo, pois os vetores de entrada são pequenos.

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License