- 問題 https://atcoder.jp/contests/abc334/tasks/abc334_c
- C問題にしては難しい!
- Kが偶数の時は自明なので省略します
- Kが奇数の時、i=0, 2, 4, 6, ... を除外した時の奇妙さをそれぞれ求めてminを取りたい。そのまま実装するとO(N2)
- まず、i=0を除外した時の解をO(N)かけて求めます
- 次に、i=2を除外した時の解を、上の解を利用してO(1)で求めます。変化する箇所がi=0,1,2しかないので、差分を見ればいいです
- i=1,2のペアを解除して、i=0,1をペアにする
code
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
ll N,K;
cin>>N>>K;
VI A(K);
rep(i, K){
cin >> A[i];
}
ll ans;
if(K%2==0){
ll sum=0;
rep(i,K/2){
ll a = A[2*i];
ll b = A[2*i+1];
sum += b-a;
}
ans=sum;
}
else{
ll sum=0;
rep(i,K/2){
ll a = A[2*i+1];
ll b = A[2*i+2];
sum += b-a;
}
ans=sum;
for(int i=2; i<K; i+=2){
ll kesu = A[i]-A[i-1];
ll tasu = A[i-1]-A[i-2];
sum -= kesu;
sum += tasu;
chmin(ans,sum);
}
}
p(ans);
return 0;
}