Puoi leggere e provare a risolvere il problema visitando la piattaforma Terry.
Osserviamo che
Sia il numero massimo di colori distinti dopo aver usato i primi colori. Dalle osservazioni precedenti, sappiamo che .
In realtà, esiste una strategia per ottenere l'uguaglianza (). L'idea è fare in modo che le prime regioni a sinistra abbiano colori distinti. Questo è possibile usando la seguente strategia:
#include <algorithm>
#include <iostream>
using namespace std;
int solve() {
int n, q;
cin >> n >> q;
int ans = 0;
for (int i = 0; i < q; i++) {
int x;
cin >> x;
ans = min(ans + 1, n - x + 1);
}
return ans;
}
int main() {
int T;
cin >> T;
for (int t = 1; t <= T; t++) {
int ans = solve();
cout << "Case #" << t << ": " << ans << "\n";
}
}