題意 ： 給你n個數字，這些數字可正可負，再給你個數字t,
求在這個數列中一個連續的子序列，和的絕對值 與t相差最小；

數據范圍較大， 考慮數字沒有負數的情況，
能夠想到用尺取法解決， （關于尺取法， 自己感受一下這東西的奇妙， 不好說， 理解了之后也沒什么好說， 實現主要是首尾指針的移動）， 那么增加了負數之后， 發現題目中要的是序列的絕對值， 發現直接排序前綴和即使用后面的前綴和減去前面的前綴和， 也沒有關系；

但主要需要注意的是本題細節比較煩， 在POJ上WA了3,4次， 這里提示一下
注意如果給出的值為0時的處理， 還有就是自己多想幾組小數據來調試， 調的很惡心， 但也很享受， 適合做尺取的好題

/* *題意：給你n個數字，這些數字可正可負，再給你個數字t, *求在這個數列中一個連續的子序列，和的絕對值 與t相差最小 * ————Galaxy TODO */ #include <cstdio> #include <algorithm>typedef long long LL;const int N = 1e5 + 10; #define C c = getchar() #define rep(i, s, t) for(int i = s; i <= t; ++i)LL abs(LL x) {return x>0?x:-x;} int read(int x=0, int t=1) {char C;while(c<'0' || c>'9') {if(c=='-') t=-1; C;}while(c>='0' && c<='9') x = x*10 + c-'0', C;return x*t; }struct Sum_tot{LL sum; int rk;//Sum_tot(int _sum, int _rk) {sum = _sum; rk = _rk;}bool operator < (const Sum_tot& rhs) const{return sum < rhs.sum;} }P[N];int main() { #ifndef ONLINE_JUDGEfreopen("input.in", "r", stdin);freopen("res.out", "w", stdout); #endifint n, T; LL S;while(scanf("%d%d", &n, &T) == 2 && n+T) {P[0].sum = 0, P[0].rk = 0;rep(i, 1, n) P[i] = ((Sum_tot) {P[i-1].sum+read(), i});std :: sort(P, P+n+1);// rep(i, 0, n) printf("%lld%c", P[i].sum, i^n?' ':'\n');while(T--) {scanf("%lld", &S);int ansl=n, ansr=n;int l = n-1, r = n;LL res = 1LL << 62;while(r > l) {// printf("%d %d__debug1\n", l, r);while(P[r].sum - P[l].sum <= S && l >= 0) { if(abs(P[r].sum-P[l].sum-S) < abs(S-res)) {res = P[r].sum - P[l].sum;ansl = P[l].rk, ansr = P[r].rk;}--l;}if(l < 0) break;// printf("%d %d__debug2\n", l, r);while(P[r].sum - P[l].sum >= S && r > l) { if(P[r].sum-P[l].sum-S < abs(res-S)) {res = P[r].sum - P[l].sum;ansl = P[l].rk, ansr = P[r].rk;}--r;}if(r < 0) break;if(l == r) --l;if(l < 0) break;// printf("%d %d__debug3\n", l, r);if(res == S) break;}if(ansl+1 > ansr) std::swap(ansl, ansr);printf("%lld %d %d\n", res, ansl+1, ansr);}}return 0; } //XXX

轉載于:https://www.cnblogs.com/pbvrvnq/p/8530155.html

總結

以上是生活随笔為你收集整理的POJ 2566 Bound Found的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。