【题意】找一个连续的子区间,使它的和的绝对值最接近k
【分析】首先尺取法需要序列满足单调性,但是这里的前缀和并不满足单调性。但是这里是求绝对值,这样的话可以给前缀数组sum排序.
因为序列绝对值abs(sum[ed]-sum[st])==abs(sum[st]-sum[ed]).
但是需要取前缀和,单个数字排序就无法获得连续序列了。然后对接近k的条件,需要把左右两个指针都随时移动(以前写的都是枚举末尾,移动左指针,这是单调队列的思想,这里不适用)。
【AC CODE】63ms
#include <cstdio> #include <cstring> #include <cctype> #include <cmath> #include <set> //#include <unordered_set> #include <queue> #include <stack> #include <vector> #include <string> #include <algorithm> using namespace std; typedef long long LL; #define rep(i,a,n) for(int i = a; i < n; i++) #define repe(i,a,n) for(int i = a; i <= n; i++) #define per(i,n,a) for(int i = n; i >= a; i--) #define clc(a,b) memset(a,b,sizeof(a)) const int INF = 0x3f3f3f3f, MAXN = 100000+10; struct NODE{ int v,id; bool operator<(const NODE &t)const{ return v < t.v; } }p[MAXN]; int a[MAXN]; int main() { #ifdef SHY freopen("d:\\1.txt", "r", stdin); #endif int n,q; while(~scanf("%d %d", &n, &q) && n+q) { p[0].v = p[0].id = 0; repe(i,1,n) scanf("%d", &a[i]),p[i].id = i,p[i].v = p[i-1].v+a[i]; sort(p,p+1+n); while(q--) { int k; scanf("%d", &k); int ans = -1,x,y,mi = INF, st = 0, ed = 1; while(st <= n && ed <= n) { int sum = p[ed].v-p[st].v; if(abs(sum-k) < mi) { mi = abs(sum-k); ans = sum; x = p[st].id,y = p[ed].id; } if(sum < k) ed++; else if(sum > k) st++; else break; if(st == ed) ed++; } if(x > y)swap(x,y); printf("%d %d %d\n",ans,x+1,y); } } return 0; }