1044 Shopping in Mars

发表于

给一串数字，子序列之和为M。
For each test case, print i-j in a line for each pair of i ≤ j such that Di + … + Dj = M. Note that if there are more than one solution, all the solutions must be printed in increasing order of i.
如果没有符合条件，使子序列之和-M最小。
If there is no solution, output i-j for pairs of i ≤ j such that Di + … + Dj >M with (Di + … + Dj −M) minimized. Again all the solutions must be printed in increasing order of i.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
using namespace std;
vector<int> sum, resultArr;
int n, m;
void Func(int i, int &j, int &tempsum) {
    int left = i, right = n;
    while(left < right) {
        int mid = (left + right) / 2;
        if(sum[mid] - sum[i-1] >= m)
            right = mid;
        else
            left = mid + 1;
            // 为什么直接从mid+1开始，因为下面的循环会一次以每个元素为头
            // 为什么不是mid，因为这时候i到mid的和小于m，那么至少要多一个mid+1才会变大
    }
    j = right;
    tempsum = sum[j] - sum[i-1];
}
int main() {
    scanf("%d%d", &n, &m);
    sum.resize(n+1);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &sum[i]);
        sum[i] += sum[i-1];
    }
    // sum[i]表示1～i的所有数字的和
    int minans = sum[n];
    for(int i = 1; i <= n; i++) {
        int j, tempsum;
        Func(i, j, tempsum);
        if(tempsum > minans) continue;
        if(tempsum >= m) {
            if(tempsum < minans) {
                resultArr.clear();
                minans = tempsum;
                // 如果发现更贴近M的子序列和，清空输出结果
            }
            resultArr.push_back(i);
            resultArr.push_back(j);
        }
    }
    for(int i = 0; i < resultArr.size(); i += 2)
        printf("%d-%d\n", resultArr[i], resultArr[i+1]);
    return 0;
}