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
    5

    2 3

    Với a = [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ới a = [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;
}