【贪心】BZOJ2666 [cqoi2012]组装

题面在这里

​

令\(x_i\)为第\(i\)种零件选择的工厂的位置 \[ \sum_{i=1}^n(x-x_i)^2 \\ n*x^2+\sum_{i=1}^nx_i^2-2x*\sum_{i=1}^nx_i \\ 当x取\frac{\sum_{i=1}^nx_i} n时，最小值为\sum_{i=1}^n x_i^2 - \frac{(\sum_{i=1}^nx_i)^2} n \] 这样只需要维护\(\sum x_i\)和\(\sum x^2_i\)两个量即可

严格证明在此

对于每种零件，先选择最左边的工厂

然后用二元组\((x,y)\)表示一次修正，把位置在\(x\)的工厂换成\(y\)

然后按照\(x+y\)升序的顺序修正当前选择的工厂集合

一起更新答案即可

感性理解：组装车间从\(-\infty\)到\(+\infty\)移动，考虑零件相同的两个相邻工厂

从选择\(x\)到选择\(y\)，交界点肯定是中点，所以要按照\(\frac{x+y} 2\)的顺序修正

​

示例程序：

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

const int maxn=100005;
int n,m,q;
vector<int> V[maxn];
struct data{
	int x,y;
	data (int _x=0,int _y=0):x(_x),y(_y) {}
	bool operator<(const data&b)const {return x+y<b.x+b.y;}
}a[maxn];
double ans,SS,S,pos=1e100;
#define sqr(x) ((double)(x)*(x))
int main (){
	scanf("%d%d",&n,&m);
	for (int i=1,x,y;i<=m;i++)
	 scanf("%d%d",&x,&y),V[y].push_back(x);
	for (int i=1;i<=n;i++)
	 if (V[i].size()){
	 	pos=min(pos,(double)V[i][0]);
	 	S+=V[i][0];
	 	SS+=sqr(V[i][0]);
	 	for (int j=1;j<V[i].size();j++)
	 	 a[++q]=data(V[i][j-1],V[i][j]);
	 }
	ans=SS-S*S/n;
	sort(a+1,a+1+q);
	for (int i=1;i<=q;i++){
		S+=a[i].y-a[i].x;
		SS+=sqr(a[i].y)-sqr(a[i].x);
		if (SS-S*S/n<ans) ans=SS-S*S/n,pos=S/n;
	}
	printf("%.4lf",pos);
	return 0;
}