Problem 2666. -- [cqoi2012]组装 -- 衡阳八中OJ离线版-2014-11-04

F.A.Qs	Home	ProblemSet	Status	Ranklist	Contest	Login	Register	捐赠本站

Notice:开心刷题：）

2666: [cqoi2012]组装

Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 232 Solved: 96
[Submit][Status]

Description

数轴上有m个生产车间可以生产零件。一共有n种零件，编号为1~n。第i个车间的坐标为x_i，生产第p_i种零件（1<=p_i<=n）。你需要在数轴上的某个位置修建一个组装车间，把这些零件组装起来。为了节约运输成本，你需要最小化cost(1)+cost(2)+…+cost(n)，其中cost(x)表示生产第x种零件的车间中，到组装车间距离的平方的最小值。

Input

输入第一行为两个整数n, m，即零件的种类数和生产车间的个数。以下m行每行两个整数x_i和p_i（1<=p_i<=n）。输入按照生产车间从左到右的顺序排列（即x_i<=x_i₊₁。注意车间位置可以重复）。输入保证每种零件都有车间生产。

Output

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

Sample Input

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

Sample Output

2.0000

HINT

编号

1-4

5-10

n

<=15

<=10000

m

<=25

<=100000

x_i

<=100

<=100,000

Source

[Submit][Status]
HOME Back