【解決方法】C++ の問題における潜在的なロジックの問題

農家のジョンは農場で N(1≤N≤2⋅10^5) 本のアスパラガスを栽培しています。 ただし、彼の植物の中には遺伝的差異があるため、一部の植物は他の植物よりも早く成長します。 i 番目の植物の最初の高さは 10 インチで、毎日後に i 番目の植物は ai インチずつ成長します。
FJ は、いくつかの植物を他の植物よりも気に入っており、特定の植物を他の植物よりも高くしたいと考えています。 彼は、0 から N−1 までのすべての整数を含む個別の値 t1……tn の配列を与え、i 番目の植物には、それよりも背の高い他の植物が正確に ti 個あるようにしたいと考えています。 FJ の要求を満たすための最小日数を見つけるか、それが不可能であると判断します。
入力：
1 つ目は、独立したテスト ケースの数を示す整数 T で構成されます (1≤T≤10)
各テスト ケースの最初の行は整数 N で構成されます。
2 行目は、i 番目の植物の初期の高さをインチ単位で示す N 個の整数 hi (1≤hi≤10^9) で構成されます。
3 行目は、i 番目の植物が毎日成長するインチ数を示す N 個の整数 ai (1≤ai≤10^9) で構成されます。
4 行目は、FJ が提供する配列を示す N 個の異なる整数 ti で構成されます。
すべてのテスト ケースにわたる N の合計が 2⋅10^5 を超えないことが保証されます。

出力：
T 行に、各テスト ケースに対する答えを別の行に出力します。 不可能な場合は-1を出力します。
この問題に関係する整数のサイズが大きいため、64 ビット整数データ型 (C/C++ の「long long」など) の使用が必要になる場合があることに注意してください。
入力例 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

サンプル出力 1:
0
3
2
5
-1
-1

最初のサンプル入力には 6 つのテスト ケースがあります。
最初のテスト ケースには植物が 1 つだけあるため、条件は 0 日目に満たされます。
2 番目のテスト ケースでは、最初のプラントが 2 番目のプラントよりも短くする必要があります。 1日目以降は高さ15と13、2日目以降は高さともに23、3日目以降は高さ31と33となり、条件を満たした初日となります。
3 番目と 4 番目のテスト ケースは 2 番目と似ています。
5 番目のテスト ケースでは、どちらの植物も初期高さ 7、成長率 8 で開始します。したがって、それらは常に同じ高さになり、したがって条件が満たされることはありません。
6 番目のテスト ケースでは、最初は条件が満たされておらず、成長率は同じです。 したがって、条件は決して満たされません。
入力例 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

サンプル出力 2:
4
7

2 番目のサンプル入力には、2 つのテスト ケースがあります。
最初のテスト ケースでは、4 日目の最終的な高さは 19、20、21、18、16 です。
2 番目のテスト ケースでは、7 日目の最終的な身長は 25、17、19、35、36 です。

私が試したこと:

次の 2 つの (非常にわずかに) 異なるコードを試してみました。
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;
}