hogloidのブログ

へなちょこ

Codeforces#148 div1B,div2D Boring Partition

URL:http://www.codeforces.com/contest/238/problem/B

問題概要

ある数列が与えられる。
これを、2つの部分列に分ける(どちらかが空でも良い)
ある2つの要素の間のコストを、2つが同じ部分列に分けられているならその和、そうでないなら和に+hしたもの(hは与えられる)と定義する。
すべての要素の間のコストの最大の差(つまり、一番大きいコスト-一番小さいコスト)の最小値はいくらか。
また、最小値を取るときどのように分けるかも出力せよ。
数列の長さ<=10^5、h<=10^8、数列の要素<=10^8

方針

貪欲
考えると、ソートしてから一番小さい要素の他を数列A,そこからいくらかまでを数列B,そのあとは再び数列A、
とするか、すべて同じ数列に入れるか、が最適
あとは、律儀に実装。
比較的頭悪い実装している・・・

using namespace std;

pair<int,int> a[100005];
int h;
int n;
int ans[100005];
int main(){
	cin>>n>>h;
	for(int i=0;i<n;++i) cin>>a[i].first,a[i].second=i;
	sort(a,a+n);

	if(n==2){
		printf("%d\n",0);
		printf("%d %d\n",1,1);
		return 0;
	}

	int res=INF;
	pair<int,int> range;
	{
		int minval=min(a[1].first+a[2].first,a[0].first+a[1].first+h),
			maxval=max(a[n-1].first+a[n-2].first,a[0].first+a[n-1].first+h);
		if(maxval-minval<res){
			res=maxval-minval;
			range=make_pair(1,n-1);
		}
	}
	{
		int minval=a[0].first+a[1].first,maxval=a[n-1].first+a[n-2].first;
		if(maxval-minval<res){
			res=maxval-minval;
			range=make_pair(0,n-1);
		}
	}

	for(int i=1;i<n-1;++i){
		int minval=min(a[0].first+a[1].first+h,a[0].first+a[i+1].first);
		if(i>=2) minval=min(minval,a[2].first+a[1].first);
		int maxval=-1;
		if(i<n-2) maxval=a[n-1].first+a[n-2].first;
		maxval=max(maxval,a[n-1].first+a[i].first+h);
		if(maxval-minval<res){
			range=make_pair(1,i);
			res=maxval-minval;
		}
	}

	printf("%d\n",res);
	for(int i=0;i<n;++i) ans[i]=1;
	for(int i=0;i<n;++i) if(range.first<=i && i<=range.second) ans[a[i].second]=2;

	for(int i=0;i<n;++i) printf("%d%c",ans[i],i==n-1?'\n':' ');

	return 0;
}