P2094 运输

题目描述

现在已知N件商品，和搬运它们其中每一件的费用。现在搬家公司老板Mr.sb决定让我们每次任意选取2件商品。然后这2件商品只算一件商品的费用。但是这个商品的搬运费用是将选出的2个商品的费用之和除以k的运算结果。如此反复。直到只收一件商品的钱。这个就是商店要付的费用。掌柜的想尽可能的少付钱，以便将更多的钱捐给希望工程。所以请你帮他计算一下最少只用付多少钱。

为什么每次合并最大的呢？

是为了让最大的最小，只有让最大的除以$k$的次数最多，才能让最大的较小。

#include<iostream>

#include<cstdio>

#include<queue>

#include<cmath>

#include<cstdlib>

#include<queue>

#define N 50005

using namespace std;

priority_queue<int,vector<int> >H;

int n,k;

int main()

{

    scanf("%d%d",&n,&k);

    for(int x,i=;i<=n;i++) {

        scanf("%d",&x);

        H.push(x);

    }

    for(int i=;i<n;i++){

        int x,y;

        x=H.top();H.pop();

        y=H.top();H.pop();

        H.push((x+y)/k);

    }

    printf("%d",H.top());

    return ;

}

巴特西

洛谷——P2094 运输

P2094 运输

题目描述

最新文章

热门文章