「题解」荷马史诗(未完待续)

#include<cstdio>
#include<cmath>
#include<algorithm>
using std::max;
#include<queue>
using std::priority_queue;
typedef long long ll;
const int MAXN=100000+5;
const int MAXK=9+5;
struct Node{
    ll val,times;
    Node(void){
        val=times=0;
        return;
    }
    Node(ll a,ll b){
        val=a,times=b;
        return;
    }
    bool operator<(const Node &a)const{
        return (val!=a.val)?(val>a.val):(times>a.times);
    }
};
int n,k;
priority_queue<Node> Q;
int main(void){
    freopen("epic.in","r",stdin);
    freopen("epic.out","w",stdout);
    register int i;
    register ll ans1=0,ans2=0;
    Node top,next;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;++i){
        static ll w;
        scanf("%lld",&w);
        Q.push(Node(w,0));
    }
    while(k>2&&n%(k-1)!=1){
        ++n;
        Q.push(Node(0,0));
    }
    while(Q.size()>1){
        next=Node(0,0);
        for(i=1;i<=k;++i){
            top=Q.top();
            Q.pop();
            next.val+=top.val;
            next.times=max(next.times,top.times+1);
        }
        ans1+=next.val;
        ans2=max((ll)ans2,next.times);
        Q.push(next);
    }
    printf("%lld\n%lld\n",ans1,ans2);
    return 0;
}