<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>Problem 1005 - Fast Food</TITLE>
<META http-equiv=Content-Type content="text/html; charset=utf-8"><LINK
href="http://acm.hit.edu.cn/ojs/ojs.css" type=text/css rel=stylesheet><LINK
href="http://acm.hit.edu.cn/ojs/prob.css" type=text/css rel=stylesheet>
<META content="MSHTML 6.00.6000.16544" name=GENERATOR></HEAD>
<BODY>
<CENTER><A href="http://acm.hit.edu.cn/OJS"><IMG
src="http://acm.hit.edu.cn/ojs/pic/banner.gif" border=0></A> </CENTER><FONT
color=red></FONT>
<CENTER class=heading>Fast Food</CENTER>
<HR>
<CENTER>
<TABLE class=default border=0>
<TBODY>
<TR>
<TD align=right>Time limit:</TD>
<TD width=50>3sec.</TD>
<TD align=right>Submitted:</TD>
<TD width=50>863</TD></TR>
<TR>
<TD align=right>Memory limit:</TD>
<TD width=50>32M</TD>
<TD align=right>Accepted:</TD>
<TD width=50>208</TD></TR></TBODY></TABLE></CENTER>
<CENTER>Source : <A
href="http://acm.hit.edu.cn/ojs/result.php?str=%22Unknown%22"><FONT
color=red>Unknown</FONT></A></CENTER>
<HR>
<CENTER>
<TABLE class=default cellSpacing=10 cellPadding=10 width="100%" border=0>
<TBODY>
<TR vAlign=top>
<TD>
<P>The fastfood chain McBurger owns several restaurants along a highway.
Recently, they have decided to build several depots along the highway,
each one located at a restaurant and supplying several of the restaurants
with the needed ingredients. Naturally, these depots should be placed so
that the average distance between a restaurant and its assigned depot is
minimized. You are to write a program that computes the optimal positions
and assignments of the depots.</P>
<P>To make this more precise, the management of McBurger has issued the
following specification: You will be given the positions of n restaurants
along the highway as n integers d1 < d2 < ... < dn (these are the
distances measured from the company's headquarter, which happens to be at
the same highway). Furthermore, a number k (k <= n) will be given, the
number of depots to be built. </P>
<P>The k depots will be built at the locations of k different restaurants.
Each restaurant will be assigned to the closest depot, from which it will
then receive its supplies. To minimize shipping costs, the total distance
sum, defined as</P>
<CENTER><IMG src="http://acm.hit.edu.cn/ojs/pic/1005_a.gif"></CENTER>
<P>must be as small as possible.</P>
<P>Write a program that computes the positions of the k depots, such that
the total distance sum is minimized. </P><B>Input</B><BR>
<P>The input file contains several descriptions of fastfood chains. Each
description starts with a line containing the two integers n and k. n and
k will satisfy 1 <= n <= 200, 1 <= k <= 30, k <= n.
Following this will n lines containing one integer each, giving the
positions di of the restaurants, ordered increasingly.</P>
<P>The input file will end with a case starting with n = k = 0. This case
should not be processed. </P><B>Output</B><BR>
<P>For each chain, first output the number of the chain. Then output a
line containing the total distance sum. </P>
<P>Output a blank line after each test case. </P><B>Sample Input </B><BR><PRE>6 3
5
6
12
19
20
27
0 0
</PRE><B>Sample Output</B><BR><PRE>Chain 1
Total distance sum = 8
</PRE></TD></TR></TBODY></TABLE>
<HR>
<CENTER class=default><A
href="http://acm.hit.edu.cn/ojs/status.php?Proid=1005&Contestid=0">Status</A>
<A
href="http://acm.hit.edu.cn/OJS/Submit?Proid=1005&Contestid=0">Submit</A>
<A
href="http://acm.hit.edu.cn/ojs/answer.php?Proid=1005">Solution</A>
<A href="http://acm.hit.edu.cn/forum/viewforum.php?f=11"><FONT
color=red>Discuss</FONT></A> </CENTER>
<HR>
<CENTER class=default>Copyright © 1998-2006, HIT ACM/ICPC Group<BR>All Rights
Reserved </CENTER></CENTER></BODY></HTML>
[返回] 计算机科学论坛 →
计算机理论与工程 → 『 算法理论与分析 』 → 一道C语言题
(订阅本版)
2007/12/12 17:50:00
新浪微博
一道C语言题
