BZOJ 2666 cqoi 2012組立貪欲

指定された数軸上のm個の点、共にn種類の色があって、数軸の上で1つの点を選択することを要求して、この点を各色の最も近い点の平方と最小に至ります
最初はすべての色の一番左の点を一番近い点として、次に「現在の点と同じ色の次の点の中点が一番左の点」を選択して置き換え、ansを更新します.
理性的証明http://www.cnblogs.com/jianglangcaijin/p/4204478.html
次は感性の証明です.
これは明らかではないか--
組立現場を-∞から+∞に移動することを考慮して一番左の点を最近接点として初期選択
移動中に職場が同じ色の次の点に近づくと、現在の点はもちろん置き換えられます.
だから、現在の点と同じ色の次の点の中点座標を左から右に置き換えるのでしょうか.の
爆発注意

#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define M 100100
using namespace std;
struct abcd{
	int pos,belong;
	bool operator < (const abcd &a) const
	{
		if(belong!=a.belong)
			return belong < a.belong;
		return pos < a.pos;
	}
}a[M];
struct _abcd{
	int pre,next;
	bool operator < (const _abcd &_) const
	{
		return pre+next < _.pre+_.next ;
	}
}b[M];
int n,m,tot;
long double ans=1e18,ans_pos;
long long sum,square_sum;
int main()
{
	int i;
	cin>>n>>m;
	for(i=1;i<=m;i++)
		scanf("%d%d",&a[i].pos,&a[i].belong);
	sort(a+1,a+m+1);
	for(i=1;i<=m;i++)
	{
		if(a[i].belong!=a[i-1].belong)
			sum+=a[i].pos,square_sum+=(long long)a[i].pos*a[i].pos;
		else
			b[++tot].pre=a[i-1].pos,b[tot].next=a[i].pos;
	}
	ans=square_sum-(long double)sum/n*sum;
	ans_pos=(long double)sum/n;
	sort(b+1,b+tot+1);
	for(i=1;i<=tot;i++)
	{
		sum-=b[i].pre;
		sum+=b[i].next;
		square_sum-=(long long)b[i].pre*b[i].pre;
		square_sum+=(long long)b[i].next*b[i].next;
		long double temp=square_sum-(long double)sum/n*sum;
		if(temp<ans)
			ans=temp,ans_pos=(long double)sum/n;
	}
	cout<<fixed<<setprecision(4)<<ans_pos<<endl;
	return 0;
}