小w与染色

发表于 |
字数统计: 297 | 阅读时长 ≈ 1
  • Code Level: ※
  • Thinking Level: ※※

Description

小W的是开染坊的。现在小W的想要把 n 块布染色。这 n 块布每一块都有一个长度 li。最初这些布都是白色的。
由于一些原因，小W进行染色的方式很奇怪。首先，他将这 n 块布任意排成一排。然后每次选择一种颜色 c 和一个参数 l，然后把所有颜色 c 的布块中前 l 块染成和剩下的分别染成两种不同从未出现过的颜色。
很明显每次染色都需要把所有颜色为 c 的布块重新染色。
小W需要把这 n 块布全部染成互不相同的颜色，他想要最小化他染色的总布块长度。

Solution

倒过来想就是石子归并

Code

1
2
3
4
5
6
7
8
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
int N; priority_queue<ll,vector<ll>,greater<ll> >Q; ll A=0,S=0;
int main(){
    int i,x; scanf("%d",&N); for(i=1;i<=N;i++) scanf("%d",&x),Q.push(x); 
    for(i=1;i<N;i++){S=Q.top();Q.pop();S+=Q.top();Q.pop();Q.push(S);A+=S;} cout<<A<<endl;
    return 0;
}