農家のジョンは農場で 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; }
解決策 1
これはと同じ問題です すべての制約についてこの問題を解決するにはどうすればよいですか[^]。 キャンディケーンが縮むのではなく、アスパラガスの成長に合わせて調整する必要があるだけです。
解決策 2
私も助けが必要なので、もしわかったら教えてください
コメント