題干：

Description

在一維坐標(biāo)軸上有許多寶藏，總共n種寶藏，每種寶藏有k個(gè)。現(xiàn)在共k個(gè)人尋寶，k個(gè)人初始位置可以位于任意點(diǎn)。但是每人需要按指定順序撿起寶藏（1->2->3->...->n，先撿第1種，再撿第2種。。。最后撿第n種寶藏，每種寶藏?fù)炱鹨粋€(gè)）。每個(gè)人要撿起n個(gè)寶藏。現(xiàn)在你自己規(guī)劃好k個(gè)人的初始位置與尋寶路線（一個(gè)寶藏只能被一個(gè)人撿起），求k個(gè)人所走路程的和最短是多少。

Input

第一行兩個(gè)整數(shù)：n,k接下來n行，每行k個(gè)整數(shù)x，表示寶藏在一維坐標(biāo)軸上的位置。

(1<=n<=100)

(1<=k<=8)

(-1000,000,000<=x<=1000,000,000)

Output

輸出一個(gè)數(shù)最短的距離和

Sample Input 1?

2 3 -1 1 3 -2 2 4

Sample Output 1

3

Hint

樣例解釋：

第一個(gè)人：從-1到-2

第二個(gè)人：從1到2

第三個(gè)人：從3到4

解題報(bào)告：

? ?貪心發(fā)現(xiàn)先對(duì)于每一個(gè)寶藏的位置排序之后每個(gè)人取對(duì)應(yīng)順序上的那個(gè)值，得到的一定是最優(yōu)解。證明也不難，交換證明法就行。

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; }

?

總結(jié)

以上是生活随笔為你收集整理的【csust】寻宝（贪心，思维）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。