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

word	meaning
chained diamonds	链式钻石
exact	adj. 精确的 v要求

• 思路 1：
  Two-Point法，用两个指针不断试探，初始时，left和right指向0（Wrong 1），right不断前进，并累加当前区间([left,right])的sum，直到sum不小于m，一旦sum不小于m,只有两种情况：
  1）if(sum==m) : 找到合适区间了，输出
  2）else : 没找到但超了，这是同样要记录这个区间（因为如果遍历结束都没有找到合适区间，就要矮子里面挑大个）
  无论是哪种情况，当区间不小于m以后要做到肯定不会是继续移动right了，所以left++（注意：随着left++,当前区间的sum减小了，所以要在left移动前把left指向元素的值减掉）

• 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：要注意这里的条件 
	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;	//第一行记录left 
				nans[1][left+1] = right+1;	//第二行记录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;
}

• 思路 2：
  一维求差->d[]（记录各点到一个起始点的距离，做差即可）用d[]记录各个i到1的距离，则j->i = d[j]-d[i] =》 d[]单调递增 =》对d[] 二分查找
  —》转化为1048Find Coins问题
  两轮遍历：第一轮 判断是否有合适区间（最小和==m），若没有求最小和 ；第二轮 输出

• 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){
//求区间[L,R)内大于x的第一个元素
	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：注意查找范围[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:条件：首先不能越界，其次，pos指向大于x的第一个元素
			Min = d[pos] - d[i-1]; 	//这里求的就是比m大的Min,所以pos不用-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;
}