Ce document présente une exploration de plusieurs techniques algorithmiques et problèmes résolus, incluant des stratégies gloutonnes et l'utilisation de tris pour l'optimisation.

Algorithmes Gloutons

1. Optimisation des Transactions (Marchandage Avide)

Ce problème concerne l'optimisation d'une série de transactions pour maximiser le gain d'une personne A disposant d'une somme initiale N. Face à M offres d'échange (acheter un objet pour x monnaie en dépensant y), si la somme restante est insuffisante, l'échange se fait proportionnellement. L'objectif est de trouver le montant maximal que A peut acquérir, avec une précision de trois décimales.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

struct Offre {
   double gain;
   double cout;
   double ratio; // gain / cout
};

bool comparerOffres(const Offre& a, const Offre& b) {
   return a.ratio > b.ratio;
}

int main() {
   int somme_initiale, nombre_offres;
   while (std::cin >> somme_initiale >> nombre_offres && (somme_initiale != -1 || nombre_offres != -1)) {
       std::vector<Offre> offres(nombre_offres);
       for (int i = 0; i < nombre_offres; ++i) {
           std::cin >> offres[i].gain >> offres[i].cout;
           offres[i].ratio = offres[i].gain / offres[i].cout;
       }

       std::sort(offres.begin(), offres.end(), comparerOffres);

       double gain_total = 0.0;
       int argent_restant = somme_initiale;

       for (const auto& offre : offres) {
           if (argent_restant >= offre.cout) {
               gain_total += offre.gain;
               argent_restant -= offre.cout;
           } else {
               gain_total += offre.ratio * argent_restant;
               argent_restant = 0;
               break;
           }
       }
       std::cout << std::fixed << std::setprecision(3) << gain_total << std::endl;
   }
   return 0;
}
   

2. Stratégie de Chevaux (Tian Ji Horse Racing)

Ce problème simule le jeu de stratégie des chevaux de Tian Ji. Étant donné le nombre de chevaux et leurs vitesses respectives pour deux joueurs, il faut déterminer la stratégie optimale pour maximiser les gains. Chaque victoire rapporte 200, chaque défaite coûte 200, et un match nul ne rapporte rien. La stratégie consiste à comparer les meilleurs chevaux ensemble, puis les meilleurs restants contre les plus faibles, et ainsi de suite, pour exploiter les avantages.

#include <iostream>
#include <vector>
#include <algorithm>

bool comparerDescendant(int a, int b) {
   return a > b;
}

int main() {
   int nombre_chevaux;
   while (std::cin >> nombre_chevaux && nombre_chevaux > 0) {
       std::vector<int> chevaux_mon = std::vector<int>(nombre_chevaux);
       std::vector<int> chevaux_adv = std::vector<int>(nombre_chevaux);

       for (int i = 0; i < nombre_chevaux; ++i) {
           std::cin >> chevaux_mon[i] >> chevaux_adv[i];
       }

       std::sort(chevaux_mon.begin(), chevaux_mon.end(), comparerDescendant);
       std::sort(chevaux_adv.begin(), chevaux_adv.end(), comparerDescendant);

       int gain_net = 0;
       int debut_mon = 0;
       int fin_mon = nombre_chevaux - 1;
       int debut_adv = 0;
       int fin_adv = nombre_chevaux - 1;

       for (int i = 0; i < nombre_chevaux; ++i) {
           if (chevaux_mon[debut_mon] > chevaux_adv[debut_adv]) {
               gain_net += 200;
               debut_mon++;
               debut_adv++;
           } else if (chevaux_mon[fin_mon] > chevaux_adv[fin_adv]) {
                gain_net += 200;
                fin_mon--;
                fin_adv--;
           }
           else { // Si le meilleur cheval de Mon est plus faible que le meilleur de Adv, on sacrifie le cheval le plus faible de Mon contre le meilleur de Adv
               gain_net -= 200;
               debut_mon++;
               fin_adv--;
           }
       }
       std::cout << gain_net << std::endl;
   }
   return 0;
}
   

3. Séquence d'Événements Maximale

Ce problème vise à trouver la plus longue séquence d'événements non superposés dans le temps. Chaque événement a une heure de début et une heure de fin. La sélection des événements doit se faire de manière à ce qu'un événement ne puisse commencer qu'après la fin du précédent. L'algorithme consiste à trier les événements par leur heure de fin, puis à sélectionner itérativement l'événement suivant qui commence après la fin du dernier événement sélectionné.

#include <iostream>
#include <vector>
#include <algorithm>

struct Event {
   int id;
   int start_time;
   int end_time;
};

bool compareEvents(const Event& a, const Event& b) {
   if (a.end_time != b.end_time) {
       return a.end_time < b.end_time;
   }
   return a.start_time > b.start_time; // Prioritize shorter events if end times are equal
}

int main() {
   int num_events;
   while (std::cin >> num_events && num_events > 0) {
       std::vector<Event> events(num_events);
       for (int i = 0; i < num_events; ++i) {
           events[i].id = i;
           std::cin >> events[i].start_time;
       }
       for (int i = 0; i < num_events; ++i) {
           std::cin >> events[i].end_time;
       }

       std::sort(events.begin(), events.end(), compareEvents);

       std::vector<int> selected_event_ids;
       int current_end_time = 0;

       for (const auto& event : events) {
           if (event.start_time >= current_end_time) {
               selected_event_ids.push_back(event.id);
               current_end_time = event.end_time;
           }
       }

       std::cout << "{";
       for (size_t i = 0; i < selected_event_ids.size(); ++i) {
           std::cout << selected_event_ids[i] << (i == selected_event_ids.size() - 1 ? "" : ",");
       }
       std::cout << "}" << std::endl;
   }
   return 0;
}
   

4. Déplacement de Meubles (Gestion des Chevauchements)

Ce problème concerne le calcul du temps nécessaire pour déplacer des meubles entre des pièces dans un bâtiment. Si plusieurs déplacements impliquent des pièces qui se chevauchent, il faut attendre que le déplacement précédent soit terminé. Chaque déplacement prend 10 minutes. L'algorithme consiste à marquer les pièces traversées par chaque déplacement et à trouver le nombre maximum de déplacements concurrents dans une pièce, qui détermine le temps total. Le code utilise un tableau pour compter l'utilisation de chaque "couloir" (intervalle de pièces).

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring> // For memset

const int MAX_ROOMS = 200; // Assuming a maximum room number

int main() {
   std::ios_base::sync_with_stdio(false);
   std::cin.tie(NULL);
   int T;
   std::cin >> T;
   while (T--) {
       int n;
       std::cin >> n;
       int room_usage[MAX_ROOMS] = {0}; // Initialize all counts to 0

       for (int i = 0; i < n; ++i) {
           int start_room, end_room;
           std::cin >> start_room >> end_room;
           // Adjust to 0-based indexing
           int u = std::min(start_room, end_room) - 1;
           int v = std::max(start_room, end_room) - 1;

           for (int j = u; j <= v; ++j) {
               room_usage[j]++;
           }
       }

       int max_concurrent_moves = 0;
       for (int i = 0; i < MAX_ROOMS; ++i) {
           if (room_usage[i] > max_concurrent_moves) {
               max_concurrent_moves = room_usage[i];
           }
       }
       std::cout << max_concurrent_moves * 10 << std::endl;
   }
   return 0;
}
   

5. Problème de Suppression de Chiffres (Sans Zéro)

Étant donné un grand entier positif (jusqu'à 240 chiffres) ne contenant pas le chiffre zéro, et un nombre s de chiffres à supprimer, l'objectif est de former le plus petit entier possible en conservant l'ordre relatif des chiffres restants. L'approche gloutonne consiste à parcourir le nombre et à supprimer le premier chiffre qui est plus grand que le chiffre suivant. Si le nombre est en ordre croissant, le dernier chiffre est supprimé. Ce prcoessus est répété s fois.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main() {
   std::string num_str;
   int s; // Number of digits to remove
   std::cin >> num_str >> s;

   std::string result = "";
   int digits_to_keep = num_str.length() - s;

   for (char digit : num_str) {
       while (!result.empty() && s > 0 && result.back() > digit) {
           result.pop_back();
           s--;
       }
       result.push_back(digit);
   }

   // If we still need to remove digits (e.g., the number was in increasing order)
   result.resize(digits_to_keep);

   // Remove leading zeros if any (though problem statement says no zeros initially)
   size_t first_digit = result.find_first_not_of('0');
   if (std::string::npos == first_digit) {
       std::cout << "0" << std::endl;
   } else {
       std::cout << result.substr(first_digit) << std::endl;
   }

   return 0;
}
   

6. Problème de Suppression de Chiffres (Avec Zéro)

Similaire au problème précédent, mais cette fois, le grand entier peut contenir des zéros. L'objectif reste de former le plus petit entier possible après suppression de s chiffres. La logique de suppression gloutonne (supprimer un chiffre s'il est supérieur au suivant) est appliquée. Une attention particulière est portée à la gestion des zéros initiaux dans le résultat final pour s'assurer que le nombre formé est valide.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main() {
   std::string num_str;
   int s; // Number of digits to remove
   std::cin >> num_str >> s;

   std::string result = "";
   int digits_to_keep = num_str.length() - s;

   for (char digit : num_str) {
       while (!result.empty() && s > 0 && result.back() > digit) {
           result.pop_back();
           s--;
       }
       result.push_back(digit);
   }

   // If we still need to remove digits (e.g., the number was in increasing order)
   result.resize(digits_to_keep);

   // Handle leading zeros
   size_t first_digit = 0;
   while (first_digit < result.length() - 1 && result[first_digit] == '0') {
       first_digit++;
   }
   std::cout << result.substr(first_digit) << std::endl;

   return 0;
}
   

7. Distribution des Voisins de Grenouilles (Réalisabilité Graphique)

Ce problème consiste à déterminer si une distribution donnée de "voisins" pour un ensemble de grenouilles est réalisable sous forme de graphe. Chaque grenouille représente un sommet, et le nombre de voisins indiqué pour une grenouille correspond au degré de ce sommet. L'algorithme utilisé est basé sur le critère d'Erdős–Gallai ou des constructions similaires pour la réalisabilité graphique. Le code implémente une approche itérative : trier les degrés restnats, prendre le plus grand degré 'd', et le diminuer de 1 pour les 'd' plus grands degrés suivants. Si à tout moment un degré devient négatif ou si la procédure ne peut être complétée, la distribution n'est pas réalisable.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

struct Frog {
   int degree;
   int original_index;
};

bool compareFrogs(const Frog& a, const Frog& b) {
   return a.degree > b.degree;
}

int main() {
   std::ios_base::sync_with_stdio(false);
   std::cin.tie(NULL);
   int T;
   std::cin >> T;
   while (T--) {
       int n;
       std::cin >> n;
       std::vector<Frog> frogs(n);
       long long sum_degrees = 0;
       for (int i = 0; i < n; ++i) {
           std::cin >> frogs[i].degree;
           frogs[i].original_index = i;
           sum_degrees += frogs[i].degree;
       }

       // Basic check: sum of degrees must be even
       if (sum_degrees % 2 != 0) {
           std::cout << "No" << std::endl;
           continue;
       }

       bool possible = true;
       int current_frog_idx = 0;
       while (current_frog_idx < n) {
           std::sort(frogs.begin() + current_frog_idx, frogs.end(), compareFrogs);

           int max_degree = frogs[current_frog_idx].degree;

           if (max_degree < 0 || max_degree > (n - 1 - current_frog_idx)) {
               possible = false;
               break;
           }

           frogs[current_frog_idx].degree = 0; // Mark as processed or connect

           for (int k = 1; k <= max_degree; ++k) {
               if (current_frog_idx + k >= n || frogs[current_frog_idx + k].degree <= 0) {
                    possible = false;
                    break;
               }
               frogs[current_frog_idx + k].degree--;
           }
            if (!possible) break;
           current_frog_idx++;
       }

       if (possible) {
           std::cout << "Yes" << std::endl;
       } else {
           std::cout << "No" << std::endl;
       }
   }
   return 0;
}
   

Tri Personnalisé avec std::sort

L'utilisation de std::sort avec une fonction de comparaison personnalisée est une technique puissante pour ordonner des structures de données complexes selon plusieurs critères. L'exemple suivant montre comment trier une liste de personnes par score (décroissant), puis par âge (décroissant) en cas d'égalité de score, et enfin par nom (alphabétique croissant) en cas d'égalité de score et d'âge.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring> // For strcmp
#include <cmath>   // For abs

struct Person {
   char name[101];
   int age;
   double score;
};

// Comparison function for sorting
bool comparePeople(const Person& a, const Person& b) {
   // Primary sort: score descending (with tolerance for floating point comparison)
   if (std::abs(a.score - b.score) > 1e-6) {
       return a.score > b.score;
   }
   // Secondary sort: age descending
   if (a.age != b.age) {
       return a.age > b.age;
   }
   // Tertiary sort: name ascending (lexicographically)
   return std::strcmp(a.name, b.name) < 0;
}

int main() {
   // Example usage:
   // std::vector<Person> people(1001); // Array to hold data
   // ... fill the 'people' vector ...
   // std::sort(people.begin(), people.end(), comparePeople);
   // ... process sorted data ...

   // Dummy example to show structure
   Person p1 = {"Alice", 20, 85.5};
   Person p2 = {"Bob", 22, 85.5};
   Person p3 = {"Charlie", 20, 90.0};
   Person p4 = {"David", 21, 85.5};

   std::vector<Person> data = {p1, p2, p3, p4};

   std::sort(data.begin(), data.end(), comparePeople);

   std::cout << "Sorted Data:\n";
   for (const auto& p : data) {
       std::cout << "Name: " << p.name << ", Age: " << p.age << ", Score: " << p.score << std::endl;
   }

   return 0;
}