1、[Problema de Programação] Torre do Circo
O funcionário da Sohu, Wang, recentemente aproveitou suas férias para viajar e em uma pequena cidade encontrou uma apresentação de circo. Após o espetáculo emocionante, ele descobriu que o diretor estava discutindo intensamente com a equipe na frante da tenda. Wang perguntou e descobriu que o circo estava planejando um novo programa "Torre Humana Mais Alta", onde artistas do circo se empilhariam para formar uma torre. Considerando fatores de segurança, exigia-se que a pessoa em cima dos ombros de alguém fosse mais baixa e mais leve que a pessoa abaixo, ou de altura e peso iguais. O diretor queria que a torre fosse a mais alta possível, mas com muitas pessoas, estava com dificuldade em como organizá-las. Wang achou que este problema era simples, então registrou a altura e peso de todos os artistas participantes e rapidamente encontrou a sequência de pessoas para formar a torre mais alta. Agora você também recebeu uma lista com altura e peso, e precisa encontrar a altura máxima da torre que pode ser formada, com os artistas numerados de 1 a N.
Descrição da Entrada:
Primeiro, um inteiro positivo N, indicando o número de pessoas.
Depois, N linhas, cada com três números, correspondendo ao número do artista, peso e altura.
Descrição da Saída:
Um inteiro m, indicando a altura da torre humana.
Exemplo de Entrada:
6<br></br>1 65 100<br></br>2 75 80<br></br>3 80 100<br></br>4 60 95<br></br>5 82 101<br></br>6 81 70
Exemplo de Saída:
4<br></br>Código abaixo:<br></br>（Nota: Após ordenar pelo peso em ordem crescente, aplicamos programação dinâmica seguindo a altura em ordem crescente. Quando os pesos são iguais, ordenar pela altura em ordem crescente garante que todos os casos de pesos iguais sejam considerados, permitindo uma melhor eficácia na seleção da programação dinâmica.）
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct artista{
int peso;
int altura;
};
bool comparar(artista a1, artista a2){
// Ordena pelo peso em ordem crescente
if(a1.peso!=a2.peso)
return a1.peso<=a2.peso;
else // Quando os pesos são iguais, coloca o mais alto primeiro
return a1.altitude>a2.altitude;
}
int main(){
int N;
int id;
int alt;
int peso;
vector<artista> artistas;
while(cin>>N){
artistas.clear();
for(int i=0;i<N;i++){
artista art;
cin>>id>>peso>>alt;
art.peso=peso;
art.altura=alt;
artistas.push_back(art);
}
sort(artistas.begin(),artistas.end(),comparar);
// Encontra a subsequência crescente máxima com base na altura
vector<int> dp(N,1);
int max_altura=0;
for(int i=1;i<N;i++){
for(int j=0;j<i;j++){
if(artistas[i].altura>=artistas[j].altura && dp[j]+1>dp[i]){
dp[i]=dp[j]+1;
}
}
}
for(int i=0;i<N;i++){
if(max_altura<dp[i])
max_altura=dp[i];
}
cout<<max_altura<<endl;
}
return 0;
}
Resultado da execução no VS2013:
<br></br><br></br>
2、[Problema de Programação] Jogo de Cartas Zha Jin Hua
Dois programadores da Sohu trabalharam por um mês sem parar e finalmente conseguiram férias. Então, decidiram jogar Zha Jin Hua para passar um tempo agradável.
Regras do jogo:
Existem 52 cartas comuns, com valores de 2,3,4,5,6,7,8,9,10,J,Q,K,A em ordem crescente, com quatro cartas de cada valor. Cada jogador recebe três cartas. Os dois jogadores comparam o valor de suas mãos, e o jogador com a mão maior vence.
As regras para os tipos de mãos são as seguintes:
1. Três cartas iguais formam um "leopardo"
2. Três cartas consecutivas formam uma "sequência" (A23 não é considerado sequência)
3. Exatamente duas cartas iguais formam um "par"
A ordem de ranking é: leopardo > sequência > par > mãos comuns
Quando os tipos de mãos são iguais, compara-se o valor numérico do tipo (por exemplo, AAA > KKK, QAK > 534, QQ2 > 10104)
Quando ambos os jogadores não têm mãos especiais, compara-se a maior carta de cada mão. Se a maior carta for igual, compara-se a segunda maior, e assim por diante (por exemplo, 37K > 89Q)
Se as mãos forem idênticas, o resultado é empate.
Descrição da Entrada:
Dois strings representando as mãos dos dois jogadores (por exemplo, "10KQ" "354"), onde o primeiro é o Jogador 1 e o segundo é o Jogador 2
Descrição da Saída:
1 indica que o Jogador 1 vence
0 indica empate
-1 indica que o Jogador 2 vence
-2 indica entrada inválida
Exemplo de Entrada:
KQ3 3Q9
10QA 6102
5810 7KK
632 74J
10102 K77
JKJ 926
68K 27A
Exemplo de Saída:
1
1
-1
-1
1
1
-1<br></br>Código abaixo:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std ;
vector<int> converter(string s){
vector<int> valores;
for ( int i = 0 ; i < s.length(); i++) {
if (s[i] == '1' && s[i+1] == '0') {
valores.push_back(10); // 1 e 0 formam um número de dois dígitos
++i;
}
else if (s[i] == 'J')
valores.push_back(11);
else if (s[i] == 'Q')
valores.push_back(12);
else if (s[i] == 'K')
valores.push_back(13);
else if (s[i] == 'A')
valores.push_back(14);
else {
int num = (int)(s[i] - '0');
valores.push_back(num);
}
}
sort (valores.begin(), valores.end());
return valores;
}
int tipo_mao(vector < int > valores){
if (valores[0] == valores[1] && valores[1] == valores[2]) {
return 3 ; // Leopardo
}
if ((valores[0] + 1 == valores[1]) && (valores[1] + 1 == valores[2])) {
return 2 ; // Sequência
}
if (valores[0] != valores[1] && valores[0] != valores[2] && valores[1] != valores[2]) {
return 0 ; // Mão comum (cartas individuais)
}
return 1 ; // Par
}
int main(){
string mao1, mao2;
while (cin >> mao1 >> mao2) {
vector < int > valores1 = converter(mao1);
vector < int > valores2 = converter(mao2);
if(valores1.size()!=3 || valores2.size()!=3){// Entrada inválida
cout<<-2<<endl;
continue;
}
int tipo1 = tipo_mao(valores1);
int tipo2 = tipo_mao(valores2);
// Comparação por tipo de mão
if (tipo1 > tipo2) {
cout << 1 << endl ;
continue;
}
if (tipo1 < tipo2) {
cout << -1 << endl ;
continue;
}
// Mesmo tipo de mão, comparação por valores
if (tipo1 == 3 && tipo2 == 3 ) { // Leopardo
if (valores1[0] > valores2[0]) {
cout << 1 << endl ;
}
else if (valores1[0] == valores2[0]) { // Mesmo valor, empate
cout << 0 << endl ;
}
else cout << -1 << endl ;
}
else if (tipo1 == 2 && tipo2 == 2 ) { // Sequência
if (valores1[0] > valores2[0]) {
cout << 1 << endl ;
}
else if (valores1[0] == valores2[0]) {
cout << 0 << endl ;
}
else cout << -1 << endl ;
}
else if (tipo1 == 1 && tipo2 == 1 ) { // Par
int par1, par2;
if (valores1[0] == valores1[1]) {
par1 = valores1[0];
}
else {
par1 = valores1[1];
}
if (valores2[0] == valores2[1]) {
par2 = valores2[0];
}
else {
par2 = valores2[1];
}
if (par1 == par2) {
int carta1, carta2;
if (par1 == valores1[0]) {
carta1 = valores1[2];
}
else carta1 = valores1[0];
if (par2 == valores2[0]) {
carta2 = valores2[2];
}
else carta2 = valores2[0];
if (carta1 > carta2) {
cout << 1 << endl ;
}
else if (carta1 < carta2) {
cout << -1 << endl ;
}
else cout << 0 << endl ;
}
else if (par1 > par2) {
cout << 1 << endl ;
}
else {
cout << -1 << endl ;
}
}
else if (tipo1 == 0 && tipo2 == 0 ) { // Mão comum
if (valores1[2] != valores2[2]) {
if (valores1[2] > valores2[2]) {
cout << 1 << endl ;
}
else {
cout << -1 << endl ;
}
}
else if (valores1[1] != valores2[1]) {
if (valores1[1] > valores2[1]) {
cout << 1 << endl ;
}
else {
cout << -1 << endl ;
}
}
else if (valores1[0] != valores2[0]) {
if (valores1[0] > valores2[0]) {
cout << 1 << endl ;
}
else if (valores1[0] < valores2[0]) {
cout << -1 << endl ;
}
}
else cout << 0 << endl ;
}
}
return 0 ;
}
Resultado da execução (no site de programação online http://www.anycodes.cn/zh/):
Entrada:
KQ3 3Q9
10QA 6102
5810 7KK
632 74J
10102 K77
JKJ 926
68K 27A
333 333
55 99
Saída:
3、[Problema de Programação] Distribuição de Bônus
A Sohu realizou um hackathon, com toda a empresa dividida em N grupos. Cada grupo ficou em uma sala dispostas em fila para começar a competição. Após o término da competição, os resultados não foram divulgados, mas cada grupo podia ver as pontuações dos dois grupos adjacentes que tinham pontuações mais baixas. Depois da competição, os bônus seriam distribuídos. Cada grupo receberá pelo menos 1 unidade de bônus (em milhares de yuanos). Além disso, se um grupo descobrir que seu bônus não é maior que o dos grupos com pontuações mais baixas, ficará insatisfeito. Como organizadores do evento, precisamos calcular o mínimo de bônus necessário para distribuir para que todos os grupos fiquem satisfeitos, com base em suas pontuações.
Descrição da Entrada:
Cada conjunto de dados começa com N, seguido por N linhas com N inteiros positivos, cada um representando a pontuação de cada grupo.
Descrição da Saída:
O mínimo de unidades de bônus (em milhares de yuanos) que precisam ser distribuídas
Exemplo de Entrada:
10
20
32
12
32
45
11
21
31
41
33
Exemplo de Saída:
20<br></br><br></br>Código abaixo:
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
int N;
while(cin>>N)
{
vector<int> pontuacoes(N);
for(int i=0;i<N;i++)
cin>>pontuacoes[i];
vector<int> bonus(N,1);
// Como cada grupo pode ver as pontuações dos grupos adjacentes com pontuações mais baixas
// Vamos da frente para trás (sentido positivo), o primeiro é inicializado com 1, e subsequentemente:
// 1. Se a pontuação do grupo i for menor que a do grupo i+1, então o grupo i+1 deve receber mais bônus: bonus[i+1]=bonus[i]+1
// 2. Se a pontuação do grupo i for igual à do grupo i+1, o bônus do grupo i+1 é definido como 1
// 3. Se a pontuação do grupo i for maior que a do grupo i+1, o bônus do grupo i+1 deve ser o menor possível, definido como 1
// Para o caso de decréscimo, podemos usar um loop reverso para atualizar
for(int i=1;i<N;i++)
{// Sentido positivo
if(pontuacoes[i]>pontuacoes[i-1])
bonus[i]=bonus[i-1]+1;
else if(pontuacoes[i]==pontuacoes[i-1])
bonus[i]=bonus[i-1];
}
for(int i=N-2;i>=0;i--)
{// Sentido reverso
if(pontuacoes[i]>pontuacoes[i+1])
bonus[i]=max(bonus[i],bonus[i+1]+1);
}
int total=0;
for(int i=0;i<N;i++)
total+=bonus[i];
cout<<total<<endl;
}
return 0;
}