[cqoi2012]组装
时间限制：3s 空间限制：128MB
题目描述
数轴上有m个生产车间可以生产零件。一共有n种零件，编号为1~n。第i个车间的坐标为xi，生产第pi种零件（1<=pi<=n）。你需要在数轴上的某个位置修建一个组装车间，把这些零件组装起来。为了节约运输成本，你需要最小化cost(1)+cost(2)+…+cost(n)，其中cost(x)表示生产第x种零件的车间中，到组装车间距离的平方的最小值。
输入格式
输入第一行为两个整数n, m，即零件的种类数和生产车间的个数。以下m行每行两个整数xi和pi（1<=pi<=n）。输入按照生产车间从左到右的顺序排列（即xi<=xi+1。注意车间位置可以重复）。输入保证每种零件都有车间生产。
输出格式
输出仅一行，即组装车间的最优位置（可以和某个生产车间重合），四舍五入保留四位小数。输入保证最优位置惟一。
样例输入
3 5 -1 3 0 1 2 3 4 2 5 2
样例输出
2.0000
提示
|
编号 |
1-4 |
5-10 |
|
n |
<=15 |
<=10000 |
|
m |
<=25 |
<=100000 |
|
xi |
<=100 |
<=100,000 |
题目来源
没有写明来源