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; }