P2094 运输

佚名 6年前 (2019-04-09) 随笔 1349人围观抢沙发百度已收录

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

这题就是合并果子（P1090）的翻版

每次找到最小的两个合并起来。用堆实现，这里用的是手写堆

代码：

// luogu-judger-enable-o2
#include<bits/stdc++.h>

using namespace std;

const int maxn=10000+10;
int n,k,heap[maxn],size=0;

void up(int p) 
{
    while(p>1)
    {
        if(heap[p]>heap[p/2])
        {
            swap(heap[p],heap[p/2]);
            p/=2;
        }
        else break;
    }
}
void insert(int val) 
{
    heap[++size]=val;
    up(size);
}//插入
void down(int p) 
{
    int s=p*2;
    while(s<=size)
    {
        if(s<size&&heap[s+1]>heap[s]) s++; 
        if(heap[s]>heap[p])
        {
            swap(heap[s],heap[p]);
            p=s; s=p*2;
        }
        else break;
    }
}
void extract() 
{
    heap[1]=heap[size--]; 
    down(1);
}//删除
int gettop() 
{
    return heap[1];
}//取堆顶
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        int a; 
        cin>>a;
        insert(a); 
    }
    while(size>=2)//如果堆里还有两个可取的数
    {
        int top1=gettop();extract();
        int top2=gettop();extract();//每次取出最小的
        insert((top1+top2)/k); 
    }
    cout<<gettop()<<endl;
    return 0;
}