题目描述
现在已知N袋猪粮品,和搬运它们其中每一袋的费用。现在猪粮公司老板Mr.锑决定让露娜每次任意选取2袋猪粮。然后这2袋猪粮只算一袋猪粮的费用。但是这袋猪粮的搬运费用是将选出的2袋猪粮的费用之和除以k的运算结果。如此反复。直到只收一袋猪粮的钱。这个就是露娜要付的费用。因为露娜很穷,所以想尽可能的少付钱。所以请萝萝帮她计算一下最少只用付多少钱。
【输入格式】trans.in
【输出格式】
【样例输入】trans.out
【样例输出】
1
输入输出格式
输入格式:
n,k w1,w2.....wn(每一件物品搬运费)
输出格式:
一个数 最少付多少钱
输入输出样例
说明
【数据规模】
n、k、wi均为非负数
n和k<=10000
【胡乱分析】
经过简单的计算发现,每次找最大的两个算取它们的费用,再找第三大的,将这个“费用”和第三大的继续算取所需的费用,以此类推,到最后只剩一袋猪粮时就会得到最小的值。然后就是代码实现了。一开始我是用数组实现的,但是只得了30分。于是想到了用STL,但是第一遍写的只能得20分,剩下8个点都是RE。然后看了一下洛谷上的题解,它用的是这个
priority_queue<int,vector<int> >q;
这个意思就是越小的整数优先级越大的优先队列。
那么代码实现如下(切了的)
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<iostream> #include<queue> #include<vector> using namespace std; priority_queue<int,vector<int> >q; int main() { int n,k,w,fee1,fee2,ans; scanf("%d%d",&n,&k); for(int i = 1;i <= n;i++) { scanf("%d",&w); q.push(w); } while(q.size() > 1) { fee1 = q.top(); q.pop(); fee2 = q.top(); q.pop(); q.push((fee1 + fee2) / k); } ans = q.top(); printf("%d",ans); return 0; }