Le fermier John cultive N(1≤N≤2⋅10^5)plants d’asperges dans sa ferme ! Cependant, certaines de ses plantes présentent des différences génétiques, de sorte que certaines plantes pousseront plus vite que d’autres. La hauteur initiale de la ième plante est de 10 cm, et après chaque jour, la ième plante grandit de 10 cm.
FJ aime certaines de ses plantes plus que d’autres, et il souhaite que certaines plantes spécifiques soient plus hautes que d’autres. Il vous donne un tableau de valeurs distinctes t1……tn contenant tous les entiers de 0 à N−1 et il veut que la ième plante ait exactement ti d’autres plantes plus hautes qu’elle. Trouvez le nombre minimum de jours pour que la demande de FJ soit satisfaite, ou déterminez que c’est impossible.
SAISIR:
Le premier sera constitué d’un entier T, désignant le nombre de cas de tests indépendants (1≤T≤10)
La première ligne de chaque scénario de test est constituée d’un nombre entier N.
La deuxième ligne se compose de N entiers hi (1≤hi≤10^9) désignant la hauteur initiale de la ième plante en pouces.
La troisième ligne se compose de N entiers ai (1≤ai≤10^9) indiquant le nombre de pouces que la ième plante pousse chaque jour.
La quatrième ligne est constituée de N entiers distincts ti désignant le tableau que FJ vous donne.
Il est garanti que la somme de N sur tous les cas de test ne dépasse pas 2⋅10^5
SORTIR:
Sortie de lignes T, la réponse à chaque scénario de test sur une ligne différente. Si ce n’est pas possible, affichez −1.
Notez que la grande taille des entiers impliqués dans ce problème peut nécessiter l’utilisation de types de données entiers de 64 bits (par exemple, un “long long” en C/C++).
EXEMPLE D’ENTRÉE 1 :
6
1
dix
1
0
2
7 3
8 10
dix
2
3 6
10 8
0 1
2
7 3
8 9
dix
2
7 7
8 8
0 1
2
7 3
8 8
dix
EXEMPLE DE SORTIE 1 :
0
3
2
5
-1
-1
Dans le premier exemple d’entrée, il y a 6 cas de test.
Dans le premier cas de test, il n’y a qu’une seule plante, donc la condition est satisfaite au jour 0.
Dans le deuxième cas de test, nous avons besoin que la première plante soit plus courte que la deuxième plante. Après le jour 1, les hauteurs sont 15 et 13. Après le jour 2, les hauteurs sont toutes deux 23. Après le jour 3, les hauteurs sont 31 et 33, et c’est le premier jour où la condition est satisfaite.
Les troisième et quatrième cas de test sont similaires au deuxième.
Dans le cinquième cas de test, les deux plantes démarrent avec une hauteur initiale de 7 et un taux de croissance de 8. Elles auront donc toujours des hauteurs identiques et la condition n’est donc jamais satisfaite.
Dans le sixième cas de test, la condition n’est pas satisfaite initialement et les taux de croissance sont les mêmes. La condition ne pourra donc jamais être satisfaite.
EXEMPLE D’ENTRÉE 2 :
2
5
7 4 1 10 12
3 4 5 2 1
2 1 0 3 4
5
4 10 12 7 1
3 1 1 4 5
2 4 3 1 0
EXEMPLE DE SORTIE 2 :
4
7
Dans le deuxième exemple d’entrée, il y a 2 cas de test.
Dans le premier cas de test, les hauteurs finales après le jour 4 sont 19, 20, 21, 18, 16.
Dans le deuxième cas de test, les hauteurs finales après le jour 7 sont 25, 17, 19, 35, 36.
Ce que j’ai essayé :
J’ai essayé ces 2 (très légèrement) codes différents :
1.
#include <iostream> #include <vector> #include <algorithm> using namespace std; bool isPossible(const vector<int>& h, const vector<int>& a, const vector<int>& t, long long days) { int n = h.size(); vector<pair<long long, int>> heights; for (int i = 0; i < n; ++i) { heights.push_back({h[i] + days * a[i], t[i]}); } sort(heights.begin(), heights.end(), greater<pair<long long, int>>()); for (int i = 0; i < n; ++i) { if (heights[i].second > i) { return false; } } return true; } long long minDays(const vector<int>& h, const vector<int>& a, const vector<int>& t) { int n = h.size(); if (n <= 1) { return 0; // No need for days if there are 0 or 1 plants. } long long low = 0, high = 1e18, result = -1; // Adjusted upper limit // Handle smaller inputs efficiently if (n <= 2) { for (long long i = 0; i <= 1e3; ++i) { if (isPossible(h, a, t, i)) { result = i; break; } } } else if (n <= 50) { for (long long i = 0; i <= 1e3; ++i) { if (isPossible(h, a, t, i)) { result = i; break; } } } else { while (low <= high) { long long mid = low + (high - low) / 2; if (isPossible(h, a, t, mid)) { result = mid; high = mid - 1; } else { low = mid + 1; } } } return result; } int main() { int T; cin >> T; while (T--) { int N; cin >> N; vector<int> h(N), a(N), t(N); for (int i = 0; i < N; ++i) { cin >> h[i]; } for (int i = 0; i < N; ++i) { cin >> a[i]; } for (int i = 0; i < N; ++i) { cin >> t[i]; } long long result = minDays(h, a, t); cout << result << endl; } return 0; }
2.
#include <iostream> #include <vector> #include <algorithm> using namespace std; bool isPossible(const vector<int>& h, const vector<int>& a, const vector<int>& t, long long days) { int n = h.size(); vector<pair<long long, int>> heights; for (int i = 0; i < n; ++i) { heights.push_back({h[i] + days * a[i], t[i]}); } sort(heights.begin(), heights.end(), greater<pair<long long, int>>()); for (int i = 0; i < n; ++i) { if (heights[i].second > i) { return false; } } return true; } long long minDays(const vector<int>& h, const vector<int>& a, const vector<int>& t) { int n = h.size(); long long low = 0, high = 2e9, result = -1; // Adjusted upper limit for large inputs // Handle smaller inputs efficiently if (n <= 2) { for (long long i = 0; i <= 2e3; ++i) { // Adjusted range for small inputs if (isPossible(h, a, t, i)) { result = i; break; } } } else if (n <= 50) { for (long long i = 0; i <= 2e3; ++i) { // Adjusted range for medium inputs if (isPossible(h, a, t, i)) { result = i; break; } } } else { while (low <= high) { long long mid = low + (high - low) / 2; if (isPossible(h, a, t, mid)) { result = mid; high = mid - 1; } else { low = mid + 1; } } } return result; } int main() { int T; cin >> T; while (T--) { int N; cin >> N; vector<int> h(N), a(N), t(N); for (int i = 0; i < N; ++i) { cin >> h[i]; } for (int i = 0; i < N; ++i) { cin >> a[i]; } for (int i = 0; i < N; ++i) { cin >> t[i]; } long long result = minDays(h, a, t); cout << result << endl; } return 0; }
Solution 1
C’est le même problème que Comment puis-je résoudre ce problème pour toutes les contraintes[^]. Il vous suffit de vous adapter à la croissance des asperges, plutôt qu’au rétrécissement des cannes de bonbon.
コメント