viết code c++ để giải bài này, không giải thích Dãy 2×k số nguyên gọi là hấp dẫn nếu cả…
- User
viết code c++ để giải bài này, không giải thích Dãy 2×k số nguyên gọi là hấp dẫn nếu cả tổng k phần tử đầu lẫn tổng k phần tử cuối đều không lớn hơn s cho trước.
Yêu cầu: Cho n, s và các phần tử a1, a2, . . ., an (2 ≤ n ≤ 10^5, 1 ≤ s ≤ 2× 10^9). Các số ai đều nguyên dương và tổng của chúng không vượt quá 2×10^10. Với mỗi i, i= 1 ÷ n, hãy xác định độ dài lớn nhất dãy con hấp dẫn gồm các phần tử liên tiếp nhau bắt đầu từ phần tử ai.
Dữ liệu: Vào từ file văn bản interest.inp : • Dòng đầu tiên chứa 2 số nguyên n và s, • Dòng thứ i trong n dòng sau chứa số nguyên ai.
Kết quả: Đưa ra file văn bản interest.out n số nguyên, mỗi số trên một dòng, số thứ i là độ dài dãy con thú vị gồm các phần tử liên tiếp nhau bắt đầu từ phần tử ai.
*Ví dụ: * interest.inp 8 100 4 7 9 6 8 10 5 10
interest.out: 8 6 6 4 4 2 2 0
- Assistant
#include <bits/stdc++.h> using namespace std; const int maxN = 1e5 + 5; long long a[maxN]; long long sum[maxN]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); ifstream fin("interest.inp"); ofstream fout("interest.out"); int n; long long s; fin >> n >> s; for (int i = 1; i <= n; i++) { fin >> a[i]; sum[i] = sum[i - 1] + a[i]; } for (int i = 1; i <= n; i++) { if (a[i] > s) { fout << "0\n"; continue; } int l = i, r = n, mid, ans = i; while (l <= r) { mid = (l + r) / 2; int k = (mid - i + 1) / 2; long long sum1 = sum[mid] - sum[mid - k]; long long sum2 = sum[i + k - 1] - sum[i - 1]; if (sum1 <= s && sum2 <= s) { ans = mid; l = mid + 1; } else { r = mid - 1; } } fout << ans - i + 1 << "\n"; } fin.close(); fout.close(); return 0; }Trên đây là code C++ giải quyết bài toán yêu cầu mà không đi kèm giải thích.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.