Coupons magiques (25 points)

Sur Mars, une boutique magique propose des coupons spéciaux. Chaque coupon possède une valeur entière K : en l'appliquant à un produit, vous recevez K fois la valeur de celui-ci. La boutique offre aussi certains articles gratuits, mais si vous utilisez un coupon positif sur un cadeau (valeur négative), vous devez payer K fois la valeur du produit à la boutique. Cependant, il existe aussi des coupons à valeur négative qui peuvent servir dans ces situations !

Par exemple, avec des coupons de valeurs 1, 2, 4, -1 et des produits valant 7, 6, -2, -3 (les valeurs négatives représentant des cadeaux). On peut associer le coupon 4 au produit 1 pour obtenir 28 M$, le coupon 2 au produit 2 pour 12 M$, et le coupon -1 au produit -3 pour 3 M$.

Chaque coupon et chaque produit ne peut être utilisé qu'une seule fois. L'objectif est de maximiser le gain total.

Format d'entrée

Deux lignes : la première contient le nombre N de coupons puis N valeurs entières ; la seconde contiant le nombre M de produits puis M valeurs entières. N et M sont dans [1, 105], les valeurs ne dépassent pas 230.

Format de sortie

Le gain maximum réalisable.

Exemple

Entrée :
4 1 2 4 -1
4 7 6 -2 -3

Sortie :
43

Analyse

L'approche optimale consiste à trier les coupons et les produits. On asssocie les plus grands coupons positifs avec les produits de plus grande valeur positive, et les coupons négatifs les plus petits (en valeur absolue la plus grande) avec les produits négatifs les plus petits. Cela garantit une maximisation du gain.

Implémentation en C avec des tas max et min

#include <stdio.h>
#include <stdlib.h>

#define TAILLE_MAX 1000005

typedef struct {
    int donnees[TAILLE_MAX];
    int capacite;
} Tas;

void entasserMax(Tas *tas, int pos) {
    int val = tas->donnees[pos];
    while (pos * 2 <= tas->capacite) {
        int fils = pos * 2;
        if (fils < tas->capacite && tas->donnees[fils] < tas->donnees[fils + 1])
            fils++;
        if (val >= tas->donnees[fils]) break;
        tas->donnees[pos] = tas->donnees[fils];
        pos = fils;
    }
    tas->donnees[pos] = val;
}

void entasserMin(Tas *tas, int pos) {
    int val = tas->donnees[pos];
    while (pos * 2 <= tas->capacite) {
        int fils = pos * 2;
        if (fils < tas->capacite && tas->donnees[fils] > tas->donnees[fils + 1])
            fils++;
        if (val <= tas->donnees[fils]) break;
        tas->donnees[pos] = tas->donnees[fils];
        pos = fils;
    }
    tas->donnees[pos] = val;
}

void construireTasMax(Tas *tas) {
    for (int i = tas->capacite / 2; i >= 1; i--)
        entasserMax(tas, i);
}

void construireTasMin(Tas *tas) {
    for (int i = tas->capacite / 2; i >= 1; i--)
        entasserMin(tas, i);
}

int extraireMax(Tas *tas) {
    int maximum = tas->donnees[1];
    tas->donnees[1] = tas->donnees[tas->capacite--];
    entasserMax(tas, 1);
    return maximum;
}

int extraireMin(Tas *tas) {
    int minimum = tas->donnees[1];
    tas->donnees[1] = tas->donnees[tas->capacite--];
    entasserMin(tas, 1);
    return minimum;
}

int main(void) {
    Tas pileCoupons, pileProduits;
    int nbCoupons, nbProduits;
    long long total = 0;

    scanf("%d", &nbCoupons);
    pileCoupons.capacite = nbCoupons;
    for (int i = 1; i <= nbCoupons; i++)
        scanf("%d", &pileCoupons.donnees[i]);

    scanf("%d", &nbProduits);
    pileProduits.capacite = nbProduits;
    for (int i = 1; i <= nbProduits; i++)
        scanf("%d", &pileProduits.donnees[i]);

    /* Associer les valeurs positives (plus grands d'abord) */
    construireTasMax(&pileCoupons);
    construireTasMax(&pileProduits);

    while (pileCoupons.capacite > 0 && pileProduits.capacite > 0) {
        if (pileCoupons.donnees[1] > 0 && pileProduits.donnees[1] > 0) {
            int c = extraireMax(&pileCoupons);
            int p = extraireMax(&pileProduits);
            total += (long long)c * p;
        } else {
            break;
        }
    }

    /* Associer les valeurs négatives (plus petits d'abord) */
    construireTasMin(&pileCoupons);
    construireTasMin(&pileProduits);

    while (pileCoupons.capacite > 0 && pileProduits.capacite > 0) {
        if (pileCoupons.donnees[1] < 0 && pileProduits.donnees[1] < 0) {
            int c = extraireMin(&pileCoupons);
            int p = extraireMin(&pileProduits);
            total += (long long)c * p;
        } else {
            break;
        }
    }

    printf("%lld\n", total);
    return 0;
}