Tôi giải quyết vấn đề C++ này

lập trình

[ad_1]

Nông dân John đang trồng N(1 FJ thích một số cây của anh ấy hơn những cây khác và anh ấy muốn một số cây cụ thể cao hơn những cây khác. Anh ta đưa cho bạn một mảng các giá trị riêng biệt t1……tn chứa tất cả các số nguyên từ 0 đến N−1 và anh ta muốn cây thứ i có chính xác ti những cây khác cao hơn nó. Tìm số ngày tối thiểu để yêu cầu của FJ được đáp ứng hoặc xác định rằng điều đó là không thể.
ĐẦ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 đầu tiên của mỗi test chứa số nguyên N.
Dòng thứ hai gồm N số nguyên hi (1 Dòng thứ ba gồm N số nguyên ai (1 Dòng thứ tư gồm N số nguyên phân biệt ti biểu thị mảng mà FJ cung cấp cho bạn.
Đả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.

[ad_2]

コメント

タイトルとURLをコピーしました