Nông dân John đang trồng N(1
ĐẦU VÀO:
Số đầu tiên sẽ bao gồm một số nguyên T, biểu thị số lượng trường hợp kiểm thử độc lập (1
Dòng thứ hai gồm N số nguyên hi (1
Đảm bảo rằng tổng N trong tất cả các trường hợp thử nghiệm không vượt quá 2⋅10^5
ĐẦU RA:
In ra T dòng, đáp án của mỗi test trên một dòng khác nhau. Nếu không thể, xuất ra −1.
Lưu ý rằng kích thước lớn của số nguyên liên quan đến vấn đề này có thể yêu cầu sử dụng loại dữ liệu số nguyên 64-bit (ví dụ: “dài dài” trong C/C++).
MẪU ĐẦU VÀO 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
MẪU ĐẦU RA 1:
0
3
2
5
-1
-1
Trong mẫu đầu vào đầu tiên, có 6 trường hợp thử nghiệm.
Trong trường hợp thử nghiệm đầu tiên, chỉ có một cây nên điều kiện được thỏa mãn vào ngày 0.
Trong trường hợp thử nghiệm thứ hai, chúng ta cần cây đầu tiên ngắn hơn cây thứ hai. Sau ngày 1, độ cao là 15 và 13. Sau ngày thứ 2, độ cao đều là 23. Sau ngày thứ 3, độ cao là 31 và 33, đó là ngày đầu tiên điều kiện được thỏa mãn.
Trường hợp thử nghiệm thứ ba và thứ tư tương tự như trường hợp thứ hai.
Trong trường hợp thử nghiệm thứ năm, cả hai cây đều bắt đầu với chiều cao ban đầu là 7 và tốc độ tăng trưởng là 8. Vì vậy, chúng sẽ luôn có chiều cao giống nhau và do đó điều kiện không bao giờ được thỏa mãn.
Trong trường hợp thử nghiệm thứ sáu, điều kiện ban đầu không được thỏa mãn và tốc độ tăng trưởng là như nhau. Vì vậy, điều kiện không bao giờ có thể được thỏa mãn.
MẪU ĐẦU VÀO 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
MẪU ĐẦU RA 2:
4
7
Trong mẫu đầu vào thứ hai, có 2 trường hợp thử nghiệm.
Trong trường hợp thử nghiệm đầu tiên, độ cao cuối cùng sau ngày thứ 4 là 19, 20, 21, 18, 16.
Trong trường hợp thử nghiệm thứ hai, độ cao cuối cùng sau ngày thứ 7 là 25, 17, 19, 35, 36.
Những gì tôi đã thử:
Đã thử 2 mã khác nhau (rất nhẹ):
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; }
Giải pháp 1
Đây là vấn đề tương tự như Làm cách nào để giải quyết vấn đề này cho tất cả các ràng buộc[^]. Bạn chỉ cần điều chỉnh cho măng tây phát triển chứ không phải để cây kẹo bị teo lại.
コメント