PKU 2062 - Card Game Cheater

Autor da análise: schultz

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

Matar uma mosca com um canhão

tmadeira 31 Mar 2009 00:20

Nossa… Que loucura pensar em usar emparelhamento máximo num problema como esse! hehehe

Re: Matar uma mosca com um canhão

schultz 31 Mar 2009 00:28

Na verdade quando eu li esse problema eu pensei em fazer emparelhamento máximo primeiro, porque com certeza ia funcionar. Mas eu fiquei pensando que não podia ser tão complicado. :-)