描述
某石油公司计划建造一条由东向西的主输油管道该管道要穿过一个有 n 口油井的油田从每口油井都要有一条输油管道沿最短路经 (或南或北) 与主管道相连如果给定 n 口油井的位置, 即它们的 x 坐标 (东西向) 和 y 坐标(南北向), 应如何确定主管道的最优位置, 即使各油井到主管道之间的输油管道长度总和最小的位置?
编程任务:
给定 n 口油井的位置, 编程计算各油井到主管道之间的输油管道最小长度总和.
格式
输入格式
输入第 1 行是油井数 n,1n10000
接下来 n 行是油井的位置, 每行 2 个整数 x 和 y,-10000x,y10000
输出格式
输出第 1 行中的数是油井到主管道之间的输油管道最小长度总和
样例 1
样例输入 1
- 5
- 1 2
- 2 2
- 1 3
- 3 -2
- 3 3
样例输出 1
6
限制
各个测试点 1s
代码
- #include < stdio.h > #include < stdlib.h >
- void bsort(int * , int);
- void swap(int * , int * );
- int main() {
- int n,
- i,
- tmp,
- a[10010],
- mid,
- sum;
- sum = 0;
- scanf("%d", &n);
- mid = n / 2;
- for (i = 0; i < n; i++) {
- scanf("%d%d", &tmp, a + i);
- }
- bsort(a, n);
- for (i = 0; i < n; i++) {
- sum += abs(a[i] - a[mid]);
- }
- printf("%d\n", sum);
- system("pause");
- return 0;
- }
- void bsort(int * a, int len) {
- int i,
- j;
- for (i = 0; i < len - 1; i++) {
- for (j = i + 1; j < len; j++) {
- if (a[i] > a[j]) {
- swap( & a[i], &a[j]);
- }
- }
- }
- }
- void swap(int * a, int * b) {
- int tmp = *a; * a = *b; * b = tmp;
- }
来源: http://www.bubuko.com/infodetail-2510677.html