Analyse du Problème

Le problème consiste à apparier les éléments de deux ensembles distincts (par exemple, les scores d'extraversion de deux groupes d'employés) de manière à maximiser la valeur minimale parmi toutes les sommes de paires formées. Pour résoudre ce défi d'optimisation, il est nécessaire d'explorer différentes stratégies algorithmiques.

Approche 1 : Recherche Dichotomique et Validation Gloutonne

La première méthode repose sur une recherche dichotomique appliquée directement sur l'epsace des réponses. Après avoir trié les deux tableaux, on définit une plage de recherche comprise entre la somme minimale possible et la somme maximale posible. À chaque itération, on évalue si une valeur médiane donnée est réalisable.

La validation de cette valeur médiane s'effectue via une stratégie gloutonne : on associe l'élément le plus faible du premier groupe avec l'élément le plus élevé du second groupe. Si toutes les paires ainsi formées atteignent ou dépassent la valeur cible, on peut tenter d'augmenter notre borne inférieure ; sinon, on réduit la borne supérieure.

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

using namespace std;

bool estValide(const vector<int>& groupeA, const vector<int>& groupeB, int cible) {
    int n = groupeA.size();
    int j = n - 1;
    for (int i = 0; i < n; ++i) {
        if (groupeA[i] + groupeB[j] < cible) {
            return false;
        }
        --j;
    }
    return true;
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    
    vector<int> hommes(n), femmes(n);
    for (int i = 0; i < n; ++i) cin >> hommes[i];
    for (int i = 0; i < n; ++i) cin >> femmes[i];
    
    sort(hommes.begin(), hommes.end());
    sort(femmes.begin(), femmes.end());
    
    int gauche = hommes[0] + femmes[0];
    int droite = hommes[n - 1] + femmes[n - 1];
    int meilleur = gauche;
    
    while (gauche <= droite) {
        int milieu = gauche + (droite - gauche) / 2;
        if (estValide(hommes, femmes, milieu)) {
            meilleur = milieu;
            gauche = milieu + 1;
        } else {
            droite = milieu - 1;
        }
    }
    
    cout << meilleur << endl;
    return 0;
}

Approche 2 : Optimisation par Tri Direct

Une analyse plus approfondie révèle que la recherche dichotomique n'est pas strictement nécessaire. En triant le premier tableau par ordre croissant et le second par ordre décroissant, on garantit naturellement que les sommes des paires correspondantes sont équilibrées. Il suffit alors de calculer ces sommes et d'en extraire le minimum, ce qui réduit considérablement la complexité temporelle et simplifie l'implémentasion.

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

using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;
    
    vector<int> hommes(n), femmes(n);
    for (int i = 0; i < n; ++i) cin >> hommes[i];
    for (int i = 0; i < n; ++i) cin >> femmes[i];
    
    sort(hommes.begin(), hommes.end());
    sort(femmes.begin(), femmes.end(), greater<int>());
    
    int score_min = hommes[0] + femmes[0];
    for (int i = 1; i < n; ++i) {
        score_min = min(score_min, hommes[i] + femmes[i]);
    }
    
    cout << score_min << endl;
    return 0;
}