viết code c++ để giải bài này, không giải thích, không ra vào từ tệp Dãy 2×k số nguyên…
- User
viết code c++ để giải bài này, không giải thích, không ra vào từ tệp 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 <iostream> #include <vector> #include <fstream> using namespace std; int main() { ifstream fin("interest.inp"); ofstream fout("interest.out"); int n, s; fin >> n >> s; vector<int> a(n + 1); for (int i = 1; i <= n; ++i) { fin >> a[i]; a[i] += a[i - 1]; // Prefix sum } vector<int> result(n + 1, 0); for (int i = 0; i < n; ++i) { int j = i + 1; // Find the longest subarray starting from i+1 while (j <= n && min(a[j] - a[i], a[n] - a[j - 1]) <= s) { ++j; } result[i] = j - i - 1; // Length of the subarray } for (int i = 1; i <= n; i++) { fout << result[i - 1] << '\n'; } fin.close(); fout.close(); return 0; }
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.