尺取法是比賽中一個很有意思的技巧。
尺取法一般要保證數(shù)列的單調(diào)性才能使用虐唠。
while(r<=n){
if(){l++}
else{r++}
}
(POJ - 2566)Bound Found
尺取法好題嫩舟，里面有尺取法的常規(guī)套路和前綴和思想醒串。
題意：給你一個整數(shù)列和一個數(shù)x，然后求出子子段宠叼，使得子段的和的絕對值（the absolute value）最接近x先巴。
分析：給你的整數(shù)列是可正可負(fù)的，不能直接用尺取法冒冬，所以我們必須做轉(zhuǎn)換伸蚯，找到單調(diào)性。但是原數(shù)列是不能動简烤，所以可以用前綴和剂邮，加入<0,0>這個點(diǎn)(一上床就懂了== 理由很簡單，如果我不加入零點(diǎn)横侦，那么我就無法求得從第一個點(diǎn)到后續(xù)任一一個點(diǎn)的和)當(dāng)然同時要記住該和是從sum[r].second-sum[l].second這一段的挥萌。
注意一下if的判斷即可，最后一個l==r是說明序列為空了枉侧。
#include<bits/stdc++.h>
#define ll long long
#define CLR(x) memset(x,0,sizeof(x))
const int maxn = 100000+100;
using namespace std;
int num[maxn];
pair<int,int>sum[maxn];
void Solve()
{
int n,k;
while(scanf("%d%d",&n,&k)!=EOF && n+k){
sum[0]=make_pair(0,0);
for(int i=1;i<=n;i++){
scanf("%d",&sum[i].first);
sum[i].first+=sum[i-1].first;
sum[i].second=i;
}
sort(sum,sum+1+n);
while(k--){
int x;
scanf("%d",&x);
int al, ar;
int l=0;
int r=1;
int res=INF;
int ans;
while(r<=n&&res){
int tmp=sum[r].first-sum[l].first;
if(abs(tmp-x)<res){
res=abs(tmp-x);
ans=tmp;
al=sum[l].second;
ar=sum[r].second;
}
if(tmp<x) r++;
if(tmp>x) l++;
if(l==r) r++;
}
printf("%d %d %d\n",ans,min(al,ar)+1,max(al,ar));
}
}
}
int main()
{
//FILEIN
//FILEOUT
//std::ios::sync_with_stdio(false);
int Case=1,cases;
//scanf("%d", &Case); cases=Case;
while(Case--){
//printf("Case #%d:",cases-Case);
Solve();
}
return 0;
}
