bzoj#P2666. [cqoi2012]组装

[cqoi2012]组装

题目描述

数轴上有 mm 个生产车间可以生产零件。一共有 nn 种零件,编号为 1n1-n。第 ii 个车间的坐标为 xix_i,生产第 pip_i 种零件(1pin1\le p_i\le n)。你需要在数轴上的某个位置修建一个组装车间,把这些零件组装起来。为了节约运输成本,你需要最小化 cost(1)+cost(2)++cost(n)cost(1)+cost(2)+\dots+cost(n),其中 cost(x)cost(x) 表示生产第 xx 种零件的车间中,到组装车间距离的平方的最小值。

输入格式

输入第一行为两个整数 n,mn,m,即零件的种类数和生产车间的个数。以下 mm 行每行两个整数 xix_ipip_i1pin1\le p_i\le n)。

输入按照生产车间从左到右的顺序排列(即 xixi+1x_i\le x_{i+1}。注意车间位置可以重复)。输入保证每种零件都有车间生产。

输出格式

输出仅一行,即组装车间的最优位置(可以和某个生产车间重合),四舍五入保留四位小数。输入保证最优位置惟一。

3 5
-1 3
0 1
2 3
4 2
5 2
2.0000

数据规模与约定

编号 131-3 474-7
nn 15\le 15 104\le 10^4
mm 25\le 25 105\le10^5
xix_i 100\le 100