Solution Officielle CF2106D

Une stratégie gloutonne existe. Chaque fois que vous voyez une fleur dans le tableau \(a\), si sa beauté est supérieure ou égale à la beauté de la fleur suivante que vous devez cueillir dans le tableau \(b\), vous la cueilez. Si nous n'insérons pas de nouvelles fleurs dans \(a\) et que nous pouvons toujours utiliser la stratégie gloutonne pour collecter toutes les \(m\) fleurs de \(b\), alors la réponse est \(0\).

Maintenant, considérons ce qui se passe si nous insérons une nouvelle fleur de beauté \(k\) dans \(a\) : cela vous permet de "sauter" certianes fleurs dans \(b\), car vous pouvez placer la nouvelle fleur insérée n'importe où dans \(a\) et la cueillir si nécessaire. Par conséquent, au lieu de considérer l'insertion d'éléments nouveaux, nous reformulons le problème comme étant la suppression d'un élément de \(b\). Une approche naïve serait d'essayer de supprimer \(b_1\), puis d'exécuter l'algorithme glouton sur \(a\) pour \(b_2, b_3, ..., b_m\), et de répéter ce processus. Nous conservons alors la plus petite valeur \(b_i\) pour laquelle l'algorithme glouton réussit après la suppression d'une fleur particulière.

#include <bits/stdc++.h>
using namespace std;

int t;
int n, m;

const int INFINI = 1e9 + 1;

bool parcoursGlouton(int sauter, const vector<int> &fleurA, const vector<int> &fleurB) {
    int indexB = 0;
    if (indexB == sauter) {
        indexB++;
    }
    for (auto x : fleurA) {
        if (x >= fleurB[indexB]) {
            indexB++;
            if (indexB == sauter) {
                indexB++;
            }
        }
        if (indexB >= m) {
            return true;
        }
    }
    return false;
}

void resoudre() {
    cin >> n >> m;
    vector<int> fleurA(n), fleurB(m);
    for (auto &x : fleurA) {
        cin >> x;
    }
    for (auto &x : fleurB) {
        cin >> x;
    }
    if (parcoursGlouton(-1, fleurA, fleurB)) {
        cout << 0;
        return;
    }
    int resultat = INFINI;
    for (int indexSaut = 0; indexSaut < m; indexSaut++) {
        if (parcoursGlouton(indexSaut, fleurA, fleurB)) {
            resultat = min(resultat, fleurB[indexSaut]);
        }
    }
    if (resultat == INFINI) {
        cout << -1;
        return;
    }
    cout << resultat;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> t;
    while (t--) {
        resoudre();
        cout << '\n';
    }

    return 0;
}

La complexité \(O(nm\) provoquera un TLE.

Optimisation

Nous devons optimiser cette partie :

for (int indexSaut = 0; indexSaut < m; indexSaut++) {
    if (parcoursGlouton(indexSaut, fleurA, fleurB)) {
        resultat = min(resultat, fleurB[indexSaut]);
    }
}

Existe-t-il un moyen de déterminer linéairement si nous pouvons supprimer la fleur \(b_i\) ?

Si la fleur \(b_i\) peut être supprimée, cela signifie que toutes les fleurs avant \(b_i\) et toutes les fleurs après \(b_i\) peuvent être satisfaites par la séquence \(a\). Pour chaque fleur \(b_i\), trouvons la plus courte sous-séquence \(a_1, a_2, ..., a_{p_i}\) qui satisfait \(b_1, b_2, ..., b_i\), et la plus courte sous-séquence \(a_{s_i}, a_{s_i+1}, ..., a_n\) qui satisfait \(b_i, b_{i+1}, ..., b_m\) . Si la fleur \(b_i\) peut être supprimée, alors la préfixe de la fleur \(b_{i-1}\) doit se terminer avant le début du suffixe de la fleur \(b_{i+1}\), c'est-à-dire \(p_{i-1}\ <\ s_{i+1}\). S'il y a chevauchement, cela signifie qu'en supprimant la fleur \(b_i\), les parties restantes ne peuvent toujours pas être satisfaites par la séquence \(a\), et la fleur \(b_i\) ne peut pas être supprimée.

Nous pouvons utiliser des pointeurs doubles pour prétraiter les préfixes et suffixes linéairement.

Code Final