[POJ] 2566Bound Found - 척취법

전송문:poj2566

문제풀이

구간 절대치에 관한 것이기 때문에 단조성이 없어서 청소할 수 없습니다...
접두사와 정렬로 바뀌어 단조성을 가지게 되었다.묘하네.

코드

#include
#include
using namespace std;
const int N=1e5+10,inf=0x7f7f7f7f;

int n,m,sum[N],rk[N],t,ans;

inline bool cmp(const int&x,const int&y){return sum[x]<sum[y];}

inline void sol()
{
	int l=0,i,res,st,ed;ans=inf;
	scanf("%d",&t);
	for(i=1;i<=n;++i){
	    if((l<i)&&((res=abs(sum[rk[i]]-sum[rk[l]]-t))<ans))
	    	ans=res,st=min(rk[i],rk[l])+1,ed=max(rk[i],rk[l]);
	    for(;l<i && sum[rk[i]]-sum[rk[l]]>=t;){
	    	l++;if(l<i && ((res=abs(sum[rk[i]]-sum[rk[l]]-t))<ans))
	    	 ans=res,st=min(rk[i],rk[l])+1,ed=max(rk[i],rk[l]);
	    }
	}
	printf("%d %d %d
",abs(sum[ed]-sum[st-1]),st,ed);
}

int main(){
	int i,j,l,r,ans,st,ed,res;
	for(;;){
	    scanf("%d%d",&n,&m);
	    if((!n)&&(!m)) break;rk[0]=0;
	    for(i=1;i<=n;++i) {scanf("%d",&sum[i]);sum[i]+=sum[i-1];rk[i]=i;}
	    sort(rk,rk+n+1,cmp);
	    for(;m;--m) sol();
	}
	return 0;
}