Problème C : Mangeur de bonbons

L'approche fondamentale consiste à trier les valeurs et, pour chaque i, sélectionner les i plus petites valeurs en plaçant les plus grandes en premier afin de réduire la pénalité au minimum. Si l'on note dp[i] la pénalité minimale obtenue avec les i premiers éléments, alors dp[i + m] = dp[i] + somme[1 : i+m], ce qui équivaut à affecter les éléments de i+1 à i+m au premier jour et à décaler les suivants d'un jour.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 2e5 + 7;

int elements[MAX_N], n, m;
ll prefix_sum[MAX_N], resultat[MAX_N];

int main() {
    scanf("%d%d", &n, &m);
    for (int idx = 1; idx <= n; idx++) scanf("%d", &elements[idx]);
    sort(elements + 1, elements + n + 1);
    for (int idx = 1; idx <= n; idx++) prefix_sum[idx] = prefix_sum[idx - 1] + elements[idx];
    for (int debut = 1; debut <= m; debut++) {
        ll position = debut, cumul = prefix_sum[debut];
        while (position <= n) {
            resultat[position] = cumul;
            position += m;
            if (position <= n) cumul += prefix_sum[position];
        }
    }
    for (int idx = 1; idx <= n; idx++) printf("%lld%c", resultat[idx], idx == n ? '\n' : ' ');
    return 0;
}

Problème D : Graphe harmonieux

La solution repose sur le tri des arêtes et l'utilisation d'une structure d'union-find pour gérer les composantes connexes. En parcourant les arêtes triées par ordre croissant, on fusionne les ensembles nécessaires pour minimiser les ajouts d'arêtes.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_M = 2e5 + 7;

pair<int, int> aretes[MAX_M];
int parent[MAX_M];

int trouver(int x) {
    return parent[x] == x ? x : parent[x] = trouver(parent[x]);
}

int main() {
    int nb_noeuds, nb_aretes;
    scanf("%d%d", &nb_noeuds, &nb_aretes);
    for (int i = 1; i <= nb_noeuds; i++) parent[i] = i;
    for (int i = 1; i <= nb_aretes; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a > b) swap(a, b);
        aretes[i] = {a, b};
        int racine_a = trouver(a);
        int racine_b = trouver(b);
        parent[racine_a] = racine_b;
    }
    sort(aretes + 1, aretes + nb_aretes + 1);
    int gauche = 0, droite = 0;
    aretes[nb_aretes + 1].first = 1e9;
    int compteur = 0;
    for (int i = 1; i <= nb_aretes + 1; i++) {
        if (aretes[i].first > droite) {
            int racine = trouver(gauche);
            for (int j = gauche + 1; j <= droite; j++) {
                int autre_racine = trouver(j);
                if (racine != autre_racine) {
                    parent[racine] = autre_racine;
                    compteur++;
                }
            }
            gauche = aretes[i].first;
            droite = aretes[i].second;
        } else {
            droite = max(droite, aretes[i].second);
        }
    }
    printf("%d\n", compteur);
    return 0;
}

Problème E : Couverture d'antenne

En triant les intervalles par leur borne gauche, on peut parcourir la séquence de gauche à droite pour calculer le coût minimal de couverture des n premiers points. La réponse finale est obtenue en évaluant la couverrture jsuqu'au point m. Cette méthode est valide car les segments qui se chevauchent respectent l'ordre des bornes gauches.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_P = 2e5 + 7;

int positions[MAX_P], portees[MAX_P], bornes_gauche[MAX_P], bornes_droite[MAX_P];
ll dp_gauche[MAX_P];
pair<int, int> intervalles[MAX_P];
int arbre_min[MAX_P << 2];

void mettre_a_jour(int idx, int valeur) {
    while (idx > 0) {
        if (valeur >= arbre_min[idx]) break;
        arbre_min[idx] = min(arbre_min[idx], valeur);
        idx -= idx & (-idx);
    }
}

int interroger(int idx, int limite) {
    if (idx == 0) return 0;
    int resultat = limite;
    while (idx <= limite) {
        resultat = min(resultat, arbre_min[idx]);
        idx += idx & (-idx);
    }
    return resultat;
}

int main() {
    int nb_antennes, longueur;
    scanf("%d%d", &nb_antennes, &longueur);
    for (int i = 1; i <= nb_antennes; i++) scanf("%d%d", &positions[i], &portees[i]);
    for (int i = 1; i <= nb_antennes; i++) {
        intervalles[i].first = max(1, positions[i] - portees[i]);
        intervalles[i].second = min(longueur, positions[i] + portees[i]);
    }
    sort(intervalles + 1, intervalles + nb_antennes + 1);
    for (int i = 1; i <= nb_antennes; i++) {
        bornes_gauche[i] = intervalles[i].first;
        bornes_droite[i] = intervalles[i].second;
    }
    for (int i = 0; i < (MAX_P << 2); i++) arbre_min[i] = longueur;
    mettre_a_jour(0, 0);
    for (int i = 1; i <= nb_antennes; i++) {
        int g = bornes_gauche[i], d = bornes_droite[i], cout = 0;
        while (g >= 1 || d <= longueur) {
            int val = interroger(g - 1, longueur);
            mettre_a_jour(d, val + cout);
            if (g == 1 && d == longueur) break;
            if (g > 1) g--;
            if (d < longueur) d++;
            cout++;
        }
    }
    printf("%d\n", interroger(longueur, longueur));
    return 0;
}

Problème F : Cheap Robot

Pas de solution fournie pour ce problème.