CTDL và giải thuật - In dãy con liên tiếp đầu tiên của dãy a sao cho tổng của dãy đó bằng s
Cho số nguyên dương n
, tiếp theo là n
số nguyên dương của một dãy a
, cuối cùng là một số s
.
In dãy con liên tiếp đầu tiên của dãy a
sao cho tổng của dãy đó bằng s
. In dãy đó ra màn hình, sau mỗi phần tử có một khoảng trắng. Nếu không tồn tại dãy đó thì in ra "-1"
.
Ví dụ:
- Test mẫu 1:
Input Output 5
1 2 3 4 5
52 3
Vớia = [1, 2, 3, 4, 5]
vàs = 5
thì kết quả mong muốn là:"2 3 "
.
- Test mẫu 2:
Input Output 3
1 2 3
4-1
Vớia = [1, 2, 3]
vàs = 4
thì kết quả mong muốn là:"-1"
Hướng dẫn bài tập.
Tạo dãy b
, với b[0] = a[0], b[i] = b[i-1] + a[i].
Ví dụ với a = [1, 2, 3, 4, 5]
và s = 5
. Dãy b được tạo ra là [1, 3, 6, 10, 15]
.
Mục đích chúng ta cần làm là cần tìm vị trí l
và i sao cho b[i] - b[l] = s
.
Như vậy dãy cần tìm sẽ là các phần tử từ ví trí l+1
đến i
ở trong dãy a
.
Dùng biến i
duyệt dãy b
, nếu b[i] ≥ s
(dãy đó có thể kết thúc tại i) tìm vị trí của b[i]-s
trong dãy b, nếu tồn tại vị trí l đó thì đưa ra dãy từ l+1
đến i
.
Code mẫu:
Ngôn ngữ C++:
#include<iostream>
using namespace std;
int a[100001];
int b[100001];
int BinSearch(int a[], int n, int x){
int l = 0, r = n-1;
while (l < r){
int mid = (l+r)/2;
if (a[mid] < x){
l = mid+1;
}
else{
r = mid;
}
}
if (a[l] == x){
return l;
}
return -1;
}
void printArray(int a[], int n, int l, int r){
for (int i = l; i <= r; i++){
cout << a[i] << " ";
}
}
bool solve(int a[], int b[], int n, int s){
b[0] = a[0];
for (int i = 1; i < n; i++){
b[i] = b[i-1] + a[i];
}
for (int i = 0; i < n; i++){
if (b[i] == s){
printArray(a, n, 0, i);
return true;
}
if (b[i] > s){
int l = BinSearch(b, n, b[i]-s);
if (l != -1){
printArray(a, n, l+1, i);
return true;
}
}
}
}
int main(){
int n, s;
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
}
cin >> s;
bool k = solve(a, b, n, s);
if (!k){
cout << -1;
}
return 0;
}