yukicoder No.198 キャンディー・ボックス２

問題はこちら
No.198 キャンディー・ボックス２ - yukicoder

手持ちのキャンディの数に制限がないとする
このとき問題は「Σ|c[i]-m|を最小化するmを求めよ」と読み替えられるので、mはc[i]の中央値とすれば良い。
（証明）
c[i]の中央値をmとする。任意のαに対して　Σ|c[i]-α|≧Σ|c[i]-m|　が成立することを示す。
必要なら全体を-1倍することでm≦αとしてよい。
m＜c[i]のとき三角不等式 ||c[i]-m|-|c[i]-α||≦|α-m| より |c[i]-α|≧|c[i]-m|-(α-m)
c[i]≦mのとき|c[i]-α|=|c[i]-m|+(α-m)
よってε=α-mとおけば
Σ|c[i]-α|≧Σ|c[i]-m|+ε(#{i|c[i]≦m}-#{i|c[i]＞m})
となる。中央値の定義から第2項のカッコ内は0以上であり、m≦αだったのでε≧0であるから
Σ|c[i]-α|≧Σ|c[i]-m|　が成立する
（証明終）
手持ちのキャンディに制限があるとき、最終的な1箱あたりの個数は(B+Σc[i])/N以下でなければならないので、結局求める答えはmin( (B+Σc[i])/N,median(c[i]))となる

ところで上の証明をよく読むと、N=2kのとき、丁寧にk番目とk+1番目を足して2でわらなくても、その間（境界含む）にある値ならばなんでも良いことがわかる
（値がεだけ変化した時、c[i]＜mなら|c[i]-m|に比べて値がε大きく、c[i]＞mならε小さくなり、中央値の定義からそれぞれの個数は同じ）

int c(int*a,int*b){return*a-*b;}
int main(){
	long b,s=0;
	int n,i,a[11];
	scanf("%ld%d",&b,&n);
	for(i=0;i<n;i++){
		scanf("%d",a+i);
		b+=a[i];
	}
	qsort(a,n,4,c);
	b/=n;
	b=b<a[n/2]?b:a[n/2];
	for(i=0;i<n;i++)s+=labs(b-a[i]);
	printf("%ld",s);
}

読み飛ばしを工夫したり配列サイズをごまかしたり型をごまかしたりといつもの短縮をして終わり

long s,q;
x,j=-2,a[9];
c(int*a,int*b){x=*a-*b;}
main(i){
	for(;~scanf("%d",a+j);q+=++j?a[j-1]:0);
	qsort(a,j,4,c);
	for(i=q/j<(i=a[j/2])?q/j:i;j--;s+=abs(a[j]-i));
	//制約上i<1e9となっているのでlabsでなくabsでよい
	j=!printf("%ld",s);
}

174B