运输

1177: (trans.in/trans.out) 运输
题目描述
现在已知 N 件商品，和搬运它们其中每一件的费用。现在搬家公司老板 Mr.sb 决定让我们每
次任意选取 2 件商品。然后这 2 件商品只算一件商品的费用。但是这个商品的搬运费用是将
选出的 2 个商品的费用之和除以 k 的运算结果。如此反复。直到只收一件商品的钱。这个就
是商店要付的费用。掌柜的想尽可能的少付钱，以便将更多的钱捐给希望工程。所以请你帮
他计算一下最少只用付多少钱。
输入
n,k
w1,w2,...,wn（每一件商品的搬运费用）
n,k<=10000
输出
最少付多少钱
样例输入
5 2
1 2 3 4 5
样例输出
1

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int cmp(int a,int b)
 7 {
 8  return a > b;
 9 }
10 int main()
11 { 
12  freopen("trans.in","r",stdin);
13  freopen("trans.out","w",stdout);
14  int i,n,k,w[10005];
15  scanf("%d %d",&n,&k);
16  for(i = 1;i <= n;i++)
17  {
18   scanf("%d",&w[i]);
19  }
20  sort(w+1,w+n+1,cmp);
21  for(i = 1;i < n;i++)
22  {
23   w[i + 1] = (w[i] + w[i + 1]) / k;
24  }
25  printf("%d",w[n]);
26  return 0;
27 }

**90分，至今没弄明白为甚扣十分叻。当初呢就是想着所有的数排个序，从大到小的每两个数除一次，这样会得到最小值（我可是算了好久才发现他是肿么把样例最小值弄成一的。。。。）