题干:
Description
在一维坐标轴上有许多宝藏,总共n种宝藏,每种宝藏有k个。现在共k个人寻宝,k个人初始位置可以位于任意点。但是每人需要按指定顺序捡起宝藏(1->2->3->...->n,先捡第1种,再捡第2种。。。最后捡第n种宝藏,每种宝藏捡起一个)。每个人要捡起n个宝藏。现在你自己规划好k个人的初始位置与寻宝路线(一个宝藏只能被一个人捡起),求k个人所走路程的和最短是多少。
Input
第一行两个整数:n,k接下来n行,每行k个整数x,表示宝藏在一维坐标轴上的位置。
(1<=n<=100)
(1<=k<=8)
(-1000,000,000<=x<=1000,000,000)
Output
输出一个数最短的距离和
Sample Input 1
2 3 -1 1 3 -2 2 4
Sample Output 1
3
Hint
样例解释:
第一个人:从-1到-2
第二个人:从1到2
第三个人:从3到4
解题报告:
贪心发现先对于每一个宝藏的位置排序之后每个人取对应顺序上的那个值,得到的一定是最优解。证明也不难,交换证明法就行。
AC代码:
#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long
struct st {
ll pos[10];
} bao[120];
bool cmp(int x,int y) {
return x<y;
}
int main() {
int n,k;
scanf ("%d%d",&n,&k);
for (int i=1; i<=n; i++)
for (int j=1; j<=k; j++)
scanf ("%lld",&bao[i].pos[j]);
for (int i=1; i<=n; i++)
sort(bao[i].pos+1,bao[i].pos+k+1,cmp);
ll ans=0;
for (int i=1; i<=k; i++)
for (int j=2; j<=n; j++){
ans+=abs(bao[j].pos[i]-bao[j-1].pos[i]);
}
printf ("%lld\n",ans);
return 0;
}