2865 - 【设计型】第11章：指针和数组 搬宿舍
搬寝室是很累的,xp深有体会.时间追述2006年7月9号,那天xp迫于无奈要从27号楼搬到3号楼,因为10号要封楼了.看着寝室里的n件物品,xp开始发呆,因为n是一个小于2000的整数,实在是太多了,于是xp决定随便搬2k件过去就行了.但还是会很累,因为2k也不小是一个不大于n的整数.幸运的是xp根据多年的搬东西的经验发现每搬一次的疲劳度是和左右手的物品的重量差的平方成正比(这里补充一句,xp每次搬两件东西,左手一件右手一件).例如xp左手拿重量为3的物品,右手拿重量为6的物品,则他搬完这次的疲劳度为(6-3)^2 = 9.现在可怜的xp希望知道搬完这2*k件物品后的最佳状态是怎样的(也就是最低的疲劳度),请告诉他吧。
Input
每组输入数据有两行,第一行有两个数n,k(2<=2*k<=n<2000).第二行有n个整数分别表示n件物品的重量(重量是一个小于2^15的正整数).在这里k的值统一为1。测试数据组数不超过8组。
Output
对应每组输入数据,输出数据只有一个表示他的最少的疲劳度,每个一行.
Examples
Input
5 1 18467 6334 26500 19169 15724 0 0
Output
492804
Solution C
#include<stdio.h> #include<stdlib.h> #define N 10 int main() { int n, k; int mim[N] = {999999999}; int count_n = 0; int i, j, k1; int c, d; int *temp; do { scanf("%d%d", &n, &k); if(n == 0) break; int *a = (int *)malloc(n*sizeof(int)); int **b = (int **)malloc(n*sizeof(int)); for(i = 0; i < n; i++) { scanf("%d", &a[i]); b[i] = &a[i]; } for(i = 0; i < n-1; i++) { k1 = i; for(j = i; j < n; j++) { if(*b[k1] > *b[j]) { k1 = j; } } if(k1 != i) { temp = b[i]; b[i] = b[k1]; b[k1] = temp; } } for(i = 0; i < n-1; i++) { c = *b[i+1] - *b[i]; d = c*c; if(d < mim[count_n]) { mim[count_n] = d; } } count_n++; }while(n); for(i = 0; i < count_n; i++) { printf("%d\n", mim[i]); } return 0; }