この回あんまり解けてないな。
https://yukicoder.me/problems/no/1391
問題
N要素の非減少整数列Aが与えられる。
整数列Bを、K要素が1で残りが-1である数列とする。
f(x) = sum(B[i]*|x-A[i]|)としたとき、任意のBを取ったときのf(x) (A[0]≦x≦A[N-1])の最小値を求めよ。
解法
x=A[i]の場合を総当たりして値を求めよう。
B[i]を1とするのは、A[i]から最寄りの値K個分なので、尺取り法の要領でそのK個の区間を動かしていこう。
int N,K; ll A[202020],S[202020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; FOR(i,N) { cin>>A[i]; S[i+1]=S[i]+A[i]; } ll ret=1LL<<60; if(K<=1) { ll a=0,b=0; FOR(i,N) { a+=-abs(A[i]-A[0]); b+=-abs(A[i]-A[N-1]); } ret=min(a,b); } else { int L=0,R=K-1; FOR(i,N) { while(R<N-1&&(A[i]-A[L])>=(A[R+1]-A[i])) R++,L++; ll tmp=((S[R+1]-S[i+1])-A[i]*(R-i))-((S[N]-S[R+1])-A[i]*(N-(R+1))); tmp+=(A[i]*(i-L)-(S[i]-S[L]))-(L*A[i]-S[L]); ret=min(ret,tmp); } } cout<<ret<<endl; }
まとめ
K=0とか注意。