题意: 有一块板子 被分为n份 每份都有一个长度
一开始板子是完好的 (也就是这n份是连在一起的) 每切一刀 代价为该板子的长度 求最小代价
一开始以为找到中间然后切就可以了 但其实是错的
其实可以反过来操作 一开始为分隔的 最后拼成一块
这样很明显就是优先队列最水的题目了
#include<iostream> #include<cstdio> #include<queue> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f const int N=10000; int main() { int n;RI(n); priority_queue<ll ,vector<ll> ,greater<ll> >q; rep(i,1,n){ll x;scanf("%lld",&x);q.push(x);} ll sum=0; while(q.size()>1) { ll a=q.top();q.pop(); ll b=q.top();q.pop(); sum+=a+b; q.push(a+b); } cout<<sum; return 0; }