yukicoder No.370 道路の掃除

問題はこちら
No.370 道路の掃除 - yukicoder

ゴミの位置をソートしておく
ゴミは連続したM個を拾うのが最短。
なぜなら両端にあるゴミを拾うために、その間にあるゴミの前を必ず通過するからである。
ということで左からi番目～i+M-1番目のゴミを拾うと考えてその最短距離を探す
もし左端と右端の座標の符号が同じなら、絶対値の大きい方だけ歩く
座標が違うなら、いったん一方まで行った後で引き返してもう一方まで行くので、絶対値の小さい方だけ重複が発生する

#define max(a,b)(a>b?a:b)
#define min(a,b)(a<b?a:b)
a[1010],i,n,m,s=1e5,t,p,q;
int c(int*a,int*b){return *a-*b;}
int main(){
	scanf("%d%d",&n,&m);
	for(i=0;i<m;i++)scanf("%d",a+i);
	qsort(a,m,4,c);
	for(i=0;i<=m-n;i++){
		p=a[i];
		q=a[i+n-1];
		if(p*q>0)t=max(abs(p),abs(q));
		else t=abs(p)+abs(q)+min(abs(p),abs(q));
		if(t<s)s=t;
	}
	printf("%d",s);
	return 0;
}

場合分けの計算式をよく考える。左端をp、右端をqとすると
・p>0なら両方とも正なのでq
・q<0なら両方とも負なので-p
・そうでないならp<=0かつq>=0なので-p+q+min(-p,q)

N,Mも配列にまとめて読み込んで、ポインタを使って縮めれば

a[1010],s=1e5,t,*q=a;
c(int*a,int*b){t=*a-*b;}
main(p){
	for(;~scanf("%d",q);q++);
	for(qsort(a+2,q-a-2,4,c);--q>a+*a;t<s?s=t:0)t=(p=q[1-*a])>0?*q:*q<0?-p:*q-p+(*q<-p?*q:-p);
	//上では左端から調べたが、ここでは右端から調べている
	s=!printf("%d",s);
}

187B

16/06/06追記
fminの存在を忘れていた

a[1010],s=1e5,t,*q=a;
c(int*a,int*b){t=*a-*b;}
main(p){
	for(;~scanf("%d",q);q++);
	for(qsort(a+2,q-a-2,4,c);--q>a+*a;t<s?s=t:0)t=(p=q[1-*a])>0?*q:*q<0?-p:*q-p+fmin(*q,-p);
	//上では左端から調べたが、ここでは右端から調べている
	s=!printf("%d",s);
}

185B