POJ-2566 : Bound Found

問題概要

長さN(<10^5)の数列が与えられる。長さ正の区間和で、絶対値がtに最も近いものを求める問題。

解法

しゃくとり法でやる。累積和をソートしておくと、http://d.hatena.ne.jp/komiyam/20120802/1343894601 でのfをf( [l,r) ) = accum[r] - accum[l] (ソート後)がt以上、とできるのでよい。

acceptされたコード

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = (int)(1e5);
const int INF = (int)(1.05e9);

int N, K, T;
int as[MAX_N];
pair<int,int> accum[MAX_N + 1];
int aa[MAX_N + 1];

bool init() {
	scanf("%d%d", &N, &K);
	for (int i = 0; i < N; ++i) {
		scanf("%d", as + i);
	}
	accum[0] = make_pair(0, 0);
	for (int i = 0; i < N; ++i) {
		accum[i+1] = make_pair(accum[i].first + as[i], i + 1);
		aa[i+1] = aa[i] + as[i];
	}
	sort(accum, accum + N + 1);
	return N > 0;
}

int update(int l, int r, int t, int& ans, int& keyFrom, int& keyTo) {
	int val = accum[r].first - accum[l].first;
	if (l >= r) {
		return -INF;
	}
	if (abs(t - val) < abs(t - ans)) {
		ans = val;
		keyFrom = min(accum[l].second, accum[r].second);
		keyTo   = max(accum[l].second, accum[r].second);
	}
	return val;
}

void proc() {
	int t;
	scanf("%d", &t);
	int ans = -INF, keyFrom = -1, keyTo = -1;
	for (int l = 0, r = 0, sum = -INF; ;) {
		for (; r < N && sum < t; sum = update(l, ++r, t, ans, keyFrom, keyTo)) ;
		if ( sum < t ) {
			break;
		}
		sum = update(++l, r, t, ans, keyFrom, keyTo);
	}

	printf("%d %d %d\n", ans, keyFrom + 1, keyTo);
}

int main() {
	for (;init();) {
		for (int _ = 0; _ < K; ++_) {
			proc();
		}
	}
	return 0;
}