Codeforces Round 218(Div.2 Only) E. Subway Innovation

Codeforces

問題

数直線（x軸）上に並んだn個の地下鉄の駅があります。各駅の座標はx[i]であらわされます。
悲しいことにこの地下鉄は財政難なので、駅をk個まで減らさないといけなくなりました。

減らし方の戦略として、kC2個の任意の2駅間距離の総和が最少になるものを選びたいです。
そうなるような駅の番号を出力してください。

制約

3≦n≦300000
2≦k≦n-1
abs(x[i])≦10^8


解法

k個の連続した（間に選ばれてない駅を挟まない）駅の選び方が最適そうなので、
とりあえず座標値で駅をソートしましょう。

したらばn-k+1個の選択肢となり、それぞれの場合の全点間距離を計算すればよさそうですが、
最小値自体ではなく、最小値を満たす選択肢を見つけられればよいので、
その差分だけを求めればよいです。

左からi個目の駅をl[i]とし、
l[i]からl[i+k-1]までのk個の駅の全点間距離をf(i,k)とすると、
f(i+1,k)-f(i,k)=
（l[i+1]からl[i+k-1]までのk-1個の点とl[i+k]との距離の総和）-
（l[i+1]からl[i+k-1]までのk-1個の点とl[i]との距離の総和）

で求められます。i番目からj番目までの座標値の総和は、1番目からj番目までの座標値の総和をO(n)で前計算しておくことでO(1)で求められます。
というわけでO(n)で最小値をとる区間を見つけられます。
この問題のように「ソートしてから考えるけど、最後にもともとの順番を出力する」ような問題は
（座標値、index）のペアでソートすると楽です。

プログラム

#include<iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<sstream>
#include<algorithm>
#include<map>
#include<complex>
#include<ctime>
#include<set>
using namespace std;


#define li			long long int
#define rep(i,to)	for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)	for(li i=(li)(start);i<((li)(to));i++)
#define pb			push_back
#define sz(v)		((li)(v).size())
#define bgn(v)		((v).begin())
#define eend(v)		((v).end())
#define allof(v)	(v).begin(), (v).end()
#define dodp(v,n)		memset(v,(li)n,sizeof(v))
#define bit(n)		(1ll<<(li)(n))
#define mp(a,b)		make_pair(a,b)
#define rin	rep(i,n)
#define EPS 1e-10
#define ETOL 1e-8
#define MOD 100000000
#define F first
#define S second
#define p2(a,b)		cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)		cout<<a<<"\t"<<b<<"\t"<<c<<endl

vector<pair<li,li> > x;
li sum[300300];

int main(){
	li n,k;
	li tmp;
	cin>>n;
	rin{
		cin>>tmp;
		x.pb(mp(tmp,i+1));
	}
	cin>>k;

	sort(allof(x));
	sum[0]=0;
	rin{
		sum[i+1]=sum[i]+x[i].F;
	}

	li mi=0;
	li idx=0;
	li now=0;

	repp(i,1,n-k+1){
		li overlap=sum[i+k-1]-sum[i];
		now-=(overlap-x[i-1].F*(k-1));
		now+=(x[i+k-1].F*(k-1)-overlap);
		if(mi>now){
			mi=now;
			idx=i;
		}
	}

	rep(i,k){
		cout<<x[idx+i].S<<" ";
	}puts("");

	return 0;
}