【贪心】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\)的顺序修正

示例程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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;
}