现在已知N件商品，和搬运它们其中每一件的费用。

现在搬家公司老板Mr.sb决定让我们每次任意选取2件商品。

然后这2件商品只算一件商品的费用。

但是这个商品的搬运费用是将选出的2个商品的费用之和除以k的运算结果。

如此反复。直到只收一件商品的钱。

这个就是商店要付的费用。

掌柜的想尽可能的少付钱，以便将更多的钱捐给希望工程。

所以请你帮他计算一下最少只用付多少钱。

n，k
w1，w2.....wn（每一件物品搬运费

一个数 最少付多少钱

C++解答

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<queue>
using namespace std;
int main()
{
	priority_queue<int>q;
	int n,k;
	cin>>n>>k;
	int x;
	for(int i=1;i<=n;++i)
	{
		cin>>x;
		q.push(x);
	}	
	for(int i=1;i<=n-1;++i)
	{
		int sum=q.top();
		q.pop();
		sum=sum+q.top();
		q.pop();
		sum=sum/k;
		q.push(sum);
	}
	
	cout<<q.top();
	return 0;
}

Java解答

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	public static void main(String[] args) {
//		long sta = System.nanoTime();
 
		InputStream is = System.in;
		OutputStream os = System.out;
 
		IN cin = new IN(is);
		PrintWriter cout = new PrintWriter(os);
 
		SO so = new SO();
		so.solution(cin, cout);
 
//		long end = System.nanoTime();
//		cout.println("耗时：" + (double)(end-sta)/1e6 + "ms");
 
		cout.close();
	}
 
	static final int MOD = (int)1e9 + 7;
	//实际代码开始的类--------------------------------------------------
	static class SO {
		void solution(IN cin, PrintWriter cout) {
			int n = cin.nextInt(), k = cin.nextInt();
			Queue<Integer> pq = new PriorityQueue<Integer>((a1,a2)->a2-a1);
			for(int i=0;i<n;++i) {
				pq.add(cin.nextInt());
			}
			int cur = 0;
			while(n>1) {
				int a = pq.remove(), b = pq.remove();
				cur = (a+b)/k;
				pq.add(cur);
				--n;
			}
			cout.println(pq.remove());
		}//end solution
	}//end SO
	
	//以下是快读部分
	static class IN {
		private BufferedReader reader;
		private StringTokenizer tokenizer;
 
		IN(InputStream is) {
			reader = new BufferedReader(new InputStreamReader(is), 32768);
			tokenizer = null;
		}
		
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
 
		public int nextInt() {
			return Integer.parseInt(next());
		}
 
		public long nextLong() {
			return Long.parseLong(next());
		}
 
		public double nextDouble() {
			return Double.parseDouble(next());
		}
 
	}
}