BZOJ2430 chocolate

有一个显然的想法是因为最后要花分成n*m个小块，所以每条边一定是要被切开的。
所以直接排序就可以了qwq,按照代价从大到小切一定是最优的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
int n,m,cur,cnt1=1,cnt2=1;
long long ans;
priority_queue<int,vector<int>,less<int> >q1,q2;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){scanf("%d",&cur);q1.push(cur);}
    for(int i=1;i<m;i++){scanf("%d",&cur);q2.push(cur);}
    while(!q1.empty()&&!q2.empty())
    {
        if(q1.top()>q2.top()){ans+=1ll*q1.top()*cnt2,cnt1++; q1.pop();}
        else{ans+=1ll*q2.top()*cnt1,cnt2++; q2.pop();}
    }
    while(!q1.empty()){ans+=1ll*q1.top()*cnt2,cnt1++; q1.pop();}
    while(!q2.empty()){ans+=1ll*q2.top()*cnt1,cnt2++; q2.pop();}
    printf("%lld\n",ans);
    return 0;
}

BZOJ2430 chocolate

原文：https://www.cnblogs.com/fengxunling/p/10275640.html