LMIO2012 cechas 题解

Edited on | In | Comments:

Problem

问题描述：

Linas的工厂需要安装微控制器与多台设备连接，以便设备之间交流控制信息。同微控制器连接的每台设备都单独使用一根电缆连接，工厂是长方形形状。所有电缆平行坐标轴铺设，左下角坐标$(0,0)$。

输入Linas每台设备的坐标和该设备电缆的单位费用。

任务:

请你编写一个程序，请帮助Linas计算安装微控制器的位置坐标，使连接所有设备的电缆花费最少。

输入格式：

第一行包含一个整数$n(1≤n≤10^6)$。表示要连接的设备有$n$台。

以下$n$行，第$i$行$3$个整数$X_i,Y_i,k_i(0≤X_i,Yi≤10^6, 1≤Ki≤10^6)$，分别表示第$i$台设备的坐标，该设备电缆的单位费用。可以多台设备共线(图中粗线)。

输出格式：

第一行是两个整数$X,Y$安装微控制器的位置坐标。第二行最小电缆费用。如果有多个答案，输出$1$个即可。

样例输入输出：

1
2
3
4
5
6
7
Input #1
5
1 1 3
4 1 3
1 2 3
2 4 3
4 4 3
1
2
3
Output #1
2 2
36

样例1解释：
Input1

1
2
3
4
5
6
7
8
9
10
Input #2
8
1 1 4
1 2 2
1 3 2
3 4 1
4 4 1
5 5 1
6 6 4
7 6 3

1
2
3
Output #2
3 4
76

样例2解释：
Input2

Solution

这道题应将横纵坐标分开讨论。

可以想到，一台单价为$k$的设备和$k$台单价为1的设备是等价的。

设微处理器横坐标为$x$,$n$台设备的坐标为$X$。这里的n指处理完后单价为1的设备的数量。

则横向上总价可以表示成：

$\sum\limits_{i=1}^n{|x-X_i|}$

于是由绝对值的几何意义（亦可以说均值不等式），将x升序排列后得：

若$n$为奇数,

则$x=X_{\frac{n+1}{2}}$;

若$n$为偶数,

则$x∈[X_{\frac{n}{2}},X_{\frac{n}{2}+1}]$。

代码：

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
38
39
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000000 + 5;
struct node{ int x, y, c; }app[MAXN];
int n, x, y;
long long sum, cnt, half;
unsigned long long cost;
int i;

unsigned long long Abs(int c, int d) { return c > d ? c - d : d - c; }
bool cmpx(node a, node b) { return a.x < b.x; }
bool cmpy(node a, node b) { return a.y < b.y; }

int main()
{
    cin >> n;
    for (i = 1; i <= n; i++) cin >> app[i].x >> app[i].y >> app[i].c, sum += app[i].c;
    half = ceil(double(sum) / 2);
    sort(app + 1, app + n + 1, cmpx);
    for (i = 1; i <= n; i++)
    {
        cnt += app[i].c;
        if (cnt >= half) break;
    }
    x = app[i].x;
    cnt = 0;
    sort(app + 1, app + n + 1, cmpy);
    for (i = 1; i <= n; i++)
    {
        cnt += app[i].c;
        if (cnt >= half) break;
    }
    y = app[i].y;
    cout << x << ' ' << y << endl;
    for (i = 1; i <= n; i++) cost += (Abs(app[i].x, x) + Abs(app[i].y, y)) * app[i].c;
    cout << cost << endl;
    return 0;
}

Data

测试数据
提取码：vf80