# 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
```

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

```5 13
2 4 5 7 9
```

### Sample Output 2:

```2-4
4-5
```
word meaning
chained diamonds Chain diamond
• 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;
}
```

Keywords: less

Added by anushka on Tue, 01 Oct 2019 01:00:31 +0300