题目链接

Bound Found POJ - 2566

思路

$$ 先把前缀和排序，然后尺取法 $$

时间复杂度

$$ O(Nlog(N)) $$

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 1e5 + 10;
int a[MAXN], id[MAXN];

bool cmp(int x, int y) {
    return a[x] < a[y];
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m), n + m) {
        id[0] = 0;
        a[0] = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);// don't forget &
            a[i] += a[i - 1];
            id[i] = i;
        }

        sort(id, id + 1 + n, cmp);

        while (m--) {
            int w;
            scanf("%d", &w);// don't forget &
            int ans1, ans2, ans3;
            ans1 = a[id[1]] - a[id[0]];
            ans2 = id[0];
            ans3 = id[1];
            int s = 0, t = 1;
            int sum = ans1;
            while (true) {
                while (t < n && (s == t || sum < w)) {
                    t++;
                    sum = a[id[t]] - a[id[s]];
                    if (abs(sum - w) < abs(ans1 - w)) {
                        ans1 = sum;
                        ans2 = id[s];
                        ans3 = id[t];
                    }
                }
                if (sum < w || s == n - 1) {
                    break;
                }
                s++;
                if (s != t) {
                    sum = a[id[t]] - a[id[s]];
                    if (abs(sum - w) < abs(ans1 - w)) {
                        ans1 = sum;
                        ans2 = id[s];
                        ans3 = id[t];
                    }
                }
            }
            if (ans2 > ans3) {
                swap(ans2, ans3);
            }
            ans2++;
            printf("%d %d %d\n", ans1, ans2, ans3);

        }
    }

    return 0;
}