PAT A1044 Shopping in Mars

Sample Input 1:

16 15
3 2 1 5 4 6 8 7 16 10 15 11 9 12 14 13

Sample Output 1:

1-5
4-6
7-8
11-11

Sample Input 2:

5 13
2 4 5 7 9

Sample Output 2:

2-4
4-5

• Train of thought 1:
  Two-Point method, using two pointers to test continuously, initially, left and right point to 0 (Wrong 1), right proceed continuously, and accumulate sum of current interval ([left,right]) until sum is not less than m. Once sum is not less than m, there are only two cases:
  1) if(sum==m): Find the appropriate interval, output
  2) Other: Not found but exceeded, this is the same to record the interval (because if you do not find the appropriate interval at the end of the traversal, you have to choose a big one in the short).
  In either case, when the interval is not less than m, right ness will not continue to move, so left ++ (Note: with left ++, the sum of the current interval decreases, so the value of the left pointing element should be subtracted before the left moves).

• code 1:

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int INF = 0x3fffffff;
int chain[110000];
int nans[5][110000];
int main(){
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; ++i){
		scanf("%d", &chain[i]);
	}
	int left = 0, right = 0, sum = chain[left];	//!!! Wrong 1: Pay attention to the conditions here. 
	int Min = INF, cnt = 0, idex = 0;
	while(right < n){
		if(sum < m){
			right++;
			sum += chain[right];
		}else{
			if(sum == m){
				printf("%d-%d\n", left+1, right+1);	
				cnt++;
			}
			else if(sum <= Min){
				Min = sum;
				nans[0][idex++] = left+1;	//First line record left 
				nans[1][left+1] = right+1;	//The second line records left-right
				nans[2][left+1] = sum; 
			} 
			sum -= chain[left];
			left++;
		} 
	}
	if(cnt == 0){
		for(int i = 0; i < idex; ++i)
			if(nans[2][nans[0][i]] == Min)
				printf("%d-%d\n", nans[0][i], nans[1][nans[0][i]]);
	}
	return 0;
}

• Train of thought 2:
  One-dimensional difference - > d [] (record the distance from each point to a starting point, make a difference) record the distance from each I to 1 with d [], then J - > I = d [j] - d [i] = d [] monotonically increasing ="search for d [] dichotomy
  Conversion to the 1048 Find Coins Problem
  Two rounds of traversal: the first round judges whether there is an appropriate interval (minimum sum== m), if there is no minimum sum; the second round of output

• code 2:

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int INF = 0x3fffffff;
int n, m, chain[110000], d[100010] = {0};
void init(){
	int sum = 0;
	for(int i = 1; i <= n; ++i){
		sum += chain[i];
		d[i] += sum;
	}
}
int upper_bound(int L, int R, int x){
//Find the first element greater than x in the interval [L,R)
	int mid;
	while(L < R){
		mid = (L + R) / 2;
		if(d[mid] > x) R = mid;
		else L = mid + 1;
	} 
	return L;
}
int main(){
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &chain[i]);
	init();
	int Min = INF;
	for(int i = 1; i <= n; ++i){
		//!!! Wrong 1: Note the search range [i, n + 1] 
		int pos = upper_bound(i, n+1, m+d[i-1]); 	// x - d[i] >= m 
		if(d[pos-1] - d[i-1] == m){
			Min = m;
			break;
		}else if(pos != n+1 && d[pos] - d[i-1] < Min){
		//Wrong 2: Conditions: First, you can't cross the boundary, and second, pos points to the first element greater than x.
			Min = d[pos] - d[i-1]; 	//This is Min larger than m, so pos doesn't need -1. 
		}
	}
	for(int i = 1; i <= n; ++i){
		int pos = upper_bound(i, n+1, Min+d[i-1]);
		if(d[pos-1] - d[i-1] == Min)
			printf("%d-%d\n", i, pos-1);
	}
	return 0;
}