Description

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

Input

输入第一行为两个整数 \(n, m\), 即零件的种类数和生产车间的个数. 以下 \(m\) 行每行两个整数 \(x_i\) 和 \(p_i (1 \leq p_i \leq n)\). 输入按照生产车间从左到右的顺序排列 (即 \(x_i \leq x_{i+1}\). 注意车间位置可以重复). 输入保证每种零件都有车间生产.

Output

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

Sample Input

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

Sample Output

2.0000

Data Range

对 40% 的数据保证:\(n \leq 15, m \leq 25, x_i \leq 100\)

对 100% 的数据保证:\(n \leq 10000, m \leq 10^5, x_i \leq 10^5\)

Solution

其实是这样的一道贪心题......

首先当你从左往右扫的时候, 会发现每一次都应该让某一种颜色的下一个位置被 (优先地) 选中, 这样选出来的情况才有意义. 然后只需要讨论一下这些临界点的中点 (在中点处距离 最小) 时候, 其他点的情况.

这样就大概排一下序, 复杂度是 \(O(m \log m)\) 的, 但是应该可以用基数排序优化一下. 考虑到本题用了 0. 5 秒 1A 掉了, 就不管优化的事情了 233

下面这个题解将我最初的猜想验证了一下, 并且给出了更详细的解 (PoPoQQQ):http://blog.csdn.net/PoPoQQQ/article/details/44758407

这不是显然么--

考虑将组装车间从-∞移动到+∞ 初始选择最左侧的点作为最近点

那么移动的过程中一旦车间离同种颜色的下一个点更近 那么当前点当然要替换了

所以是按照当前点和同种颜色的下一个点的中点坐标从左到右替换嘛......

小心爆 long long

注意刚才那个题解是感性证明 (口头 QED), 下面的是理性证明 (本人数学蒟蒻, 看不懂):http://www.cnblogs.com/jianglangcaijin/p/4204478.html

只有链接, 中间东西太多了, 不想 Ctrl+C 了

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long lli;
typedef long double llf;
const int maxn = 1010, maxm = 100100;

////////////////////////////////////////////////////////////////////////////////
// Sorting for actual positions, at first preprocessing
struct srtra { lli pos, belong; } srta[maxm];
bool operator < (srtra a, srtra b) {
    if (a.belong != b.belong) return a.belong < b.belong;
    return a.pos < b.pos; }

////////////////////////////////////////////////////////////////////////////////
// Sorting for decision changing points, at second preprocessing
struct srtrb { lli prev, next; } srtb[maxm];
bool operator < (srtrb a, srtrb b) {
    return a.prev + a.next < b.prev + b.next; }

int n, m, tot;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%lld%lld", &srta[i].pos, &srta[i].belong);
    sort(srta + 1, srta + 1 + m);
    // Assigning positions locators for all colours
    tot = 0; // Count of to-be-chosen positions, should equal to $m-n$
    // And the required, preprocessing sum of all data
    lli pos_sum = 0, // $\sum pos_i$
        sqr_sum = 0, // $\sum pos_i^2 $
        res = 1e18; // Corresponding sqr_sum for final result
    llf res_pos = 0.0; // Final result
    for (int i = 1; i <= m; i++) {
        if (srta[i].belong != srta[i - 1].belong) {
            pos_sum += srta[i].pos;
            sqr_sum += srta[i].pos * srta[i].pos;
        } else {
            srtb[++tot].prev = srta[i - 1].pos;
            srtb[tot].next = srta[i].pos;
        }
    }
    sort(srtb + 1, srtb + 1 + tot);
    res = sqr_sum - (llf)pos_sum * pos_sum / n;
    res_pos = (llf)pos_sum / n;
    // Evaluating through all possibilities
    for (int i = 1; i <= tot; i++) {
        // Updating pos_sum
        pos_sum -= srtb[i].prev;
        pos_sum += srtb[i].next;
        // Updating sqr_sum
        sqr_sum -= srtb[i].prev * srtb[i].prev;
        sqr_sum += srtb[i].next * srtb[i].next;
        // Updating res
        lli tmp_res = sqr_sum - (llf)pos_sum * pos_sum / n;
        if (tmp_res < res) {
            res = tmp_res;
            res_pos = (llf)pos_sum / n;
        }
    }
    // Output results
    printf("%.4Lf\n", res_pos);
    return 0;
}