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; }