当前位置:首页 >> 学科竞赛 >>

lith2012 cechas微控制器的车间


lith2012 cechas 微控制器的车间 问题描述:
Linas 的工厂需要安装微控制器与多台设备连接,以便设备之间交流控制信息。同微控制器连接的每台设备 都单独使用一根电缆连接,工厂是长方形形状。所有电缆平行坐标轴铺设,左下角坐标(0,0)。 输入 Linas 每台设备的坐标和该设备电缆的单位费用。

任务:
请你编写一个程序,请帮

助 Linas 计算安装微控制器的位置坐标,使连接所有设备的电缆花费最少。

输入格式:
第一行包含一个整数 n(1 ? n ? 10,000)。表示要连接的设备有 n 台。 以下 n 行,第 i 行 3 个整数 Xi,Yi,ki(0 ? Xi,Yi ? 1,000,000, 1 ? Ki ? 1,000,000),分别表示第 i 台设 备的坐标,该设备电缆的单位费用。可以多台设备共线(图中粗线)。

输出格式:
第一行是两个整数 X,Y 安装微控制器的位置坐标。第二行最小电缆费用。如果有多个答案,配合输出微控 制器的位置坐标。

样例输入输出:
Pastele1.in 5 1 4 1 2 4 1 1 2 4 4 3 3 3 3 3 Pastele1.out 22 36 样例 1 解释

这是唯一的解决方案。 Pastele2.in 8 1 1 1 3 4 5 6 7 1 2 3 4 4 5 6 6 4 2 2 1 1 1 4 3 Pastele2.out 34 76 样例 2 解释

另一种解决方案:坐标位置(4,4)。

- 1 –

2012-05-18

lith2012 cechas 微控制器的车间
const maxn=100000; maxm=1000000; var dx,dy:array[0..maxm] of int64; curx,cury,deltax,deltay:int64; i,j,xv,yv,n,x,y,k:longint; begin assign(input,'cechas.in');reset(input); assign(output,'cechas.out');rewrite(output); readln(n); for i:=0 to n-1 do begin readln(x,y,k); deltax:=deltax-k; deltay:=deltay-k; dx[x]:=dx[x]+2*k; dy[y]:=dy[y]+2*k; curx:=curx+int64(x)*int64(k); cury:=cury+int64(y)*int64(k); end; for xv:=0 to maxm-1 do begin deltax:=deltax+dx[xv]; if deltax>=0 then break; curx:=curx+deltax; end; for yv:=0 to maxm-1 do begin deltay:=deltay+dy[yv]; if deltay>=0 then break; cury:=cury+deltay; end; writeln(xv,' ',yv);writeln(curx+cury); close(input);close(output); end.

- 2 –

2012-05-18


相关文章:
lith2012 cechas微控制器的车间
lith2012 cechas微控制器的车间lith2012 cechas微控制器的车间隐藏>> lith2012 cechas 微控制器的车间 问题描述: Linas 的工厂需要安装微控制器与多台设备连接,...
更多相关标签:
lithromantic | lithromantic百度百科 | lithromantic翻译 | lithtech引擎 | lithromantic怎么读 | lithromantic什么意思 | lithromatic | 性取向lithromantic |