Petani John menanam N(1≤N≤2⋅10^5)tanaman asparagus di pertaniannya! Namun beberapa tanamannya mempunyai perbedaan genetik, sehingga beberapa tanaman akan tumbuh lebih cepat dibandingkan yang lain. Ketinggian awal tanaman ke-i adalah beberapa inci, dan setelah setiap hari, tanaman ke-i tumbuh beberapa inci.
FJ lebih menyukai beberapa tanamannya daripada yang lain, dan dia ingin beberapa tanaman tertentu lebih tinggi dari yang lain. Dia memberi Anda serangkaian nilai berbeda t1……tn berisi semua bilangan bulat dari 0 hingga N−1 dan dia ingin tanaman ke-i memiliki tepat ti tanaman lain yang lebih tinggi darinya. Tentukan jumlah hari minimum agar permintaan FJ dipenuhi, atau tentukan bahwa hal tersebut tidak mungkin.
MEMASUKKAN:
Yang pertama akan terdiri dari bilangan bulat T, yang menunjukkan jumlah kasus uji independen (1≤T≤10)
Baris pertama dari setiap kasus uji terdiri dari bilangan bulat N.
Baris kedua terdiri dari N bilangan bulat hi (1≤hi≤10^9) yang menunjukkan tinggi awal tanaman ke-i dalam inci.
Baris ketiga terdiri dari N bilangan bulat ai (1≤ai≤10^9) yang menunjukkan jumlah inci pertumbuhan tanaman ke-i setiap hari.
Baris keempat terdiri dari N bilangan bulat berbeda yang menunjukkan array yang diberikan FJ kepada Anda.
Dijamin bahwa jumlah N pada semua kasus uji tidak melebihi 2⋅10^5
KELUARAN:
Output baris T, jawaban setiap test case pada baris yang berbeda. Jika tidak memungkinkan, keluarkan −1.
Perhatikan bahwa bilangan bulat berukuran besar yang terlibat dalam masalah ini mungkin memerlukan penggunaan tipe data bilangan bulat 64-bit (misalnya, “panjang” di C/C++).
CONTOH MASUKAN 1:
6
1
10
1
0
2
7 3
8 10
1 0
2
3 6
10 8
0 1
2
7 3
8 9
1 0
2
7 7
8 8
0 1
2
7 3
8 8
1 0
CONTOH KELUARAN 1:
0
3
2
5
-1
-1
Pada input sampel pertama terdapat 6 kasus uji.
Pada uji kasus pertama hanya terdapat satu tanaman sehingga kondisi terpenuhi pada hari ke 0.
Pada uji kasus kedua, kita membutuhkan tanaman pertama lebih pendek dari tanaman kedua. Setelah hari ke-1, tingginya menjadi 15 dan 13. Setelah hari ke-2, tingginya keduanya menjadi 23. Setelah hari ke-3, tingginya menjadi 31 dan 33, dan itulah hari pertama kondisi terpenuhi.
Kasus uji ketiga dan keempat serupa dengan kasus uji kedua.
Pada uji kasus kelima, kedua tanaman memulai dengan tinggi awal 7 dan laju pertumbuhan 8. Jadi keduanya akan selalu mempunyai tinggi yang sama, sehingga syaratnya tidak pernah terpenuhi.
Dalam kasus uji keenam, kondisi awalnya tidak terpenuhi dan tingkat pertumbuhannya sama. Jadi kondisinya tidak pernah bisa dipenuhi.
CONTOH MASUKAN 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
CONTOH KELUARAN 2:
4
7
Pada input sampel kedua terdapat 2 kasus uji.
Pada kasus uji pertama, ketinggian akhir setelah hari ke 4 adalah 19, 20, 21, 18, 16.
Pada kasus uji kedua, ketinggian akhir setelah hari ke 7 adalah 25, 17, 19, 35, 36.
Apa yang saya coba:
Mencoba 2 (sedikit) kode berbeda ini:
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; }
Solusi 1
Ini adalah masalah yang sama dengan Bagaimana cara mengatasi masalah ini untuk semua kendala[^]. Anda hanya perlu menyesuaikan pertumbuhan asparagus, bukan pertumbuhan batang permen.
コメント