UVALive 7274 Canvas Painting （优先队列）-白红宇

UVALive 7274 Canvas Painting （优先队列）

阅读量：5102 次

发布时间：2019-06-13

本文共 1935 字，大约阅读时间需要 6 分钟。

Canvas Painting

题目链接：

Description

Input

The first line consists of a single integer T, the number of test cases. Each test case is composed by

two lines. The first line consists of a single integer N representing the number of canvasses. The next

line contains N space separated integers representing the sizes of the canvasses.

Constraints:

1 ≤ T ≤ 100 Number of test cases.

1 ≤ Ni ≤ 100 000 Number of canvasses in the i

th test case.

1 ≤ s ≤ 100 000 Size of each canvas.

1 ≤ ∑Ti=1 Ni ≤ 100 000 Number of canvasses over all test cases in one test file.

Output

The output contains T lines, one for each test case: the minimum amount of ink the machine needs in

order to have all canvasses with different colors.

Sample Input

7 4 7

5 3 7 5

Sample Output

题意：

给出N张白布(顺序不定).

每次选出其中同一种颜色的若干张布染上某种跟之前不同的色，这种颜色剩下的布染上另一种颜色.

每次染色的花费是布的大小.

求要将N张布都染成不同的颜色的最小花费.

题解：

一开始想的是面积大的布染尽量少的次数，先降序排列，对后缀和求和. 这个思路并不正确. (比如样例2)

这个问题反过来看就比较简单了：

最后的结果是N张颜色各异的布，反向过程是每次选出两种颜色不同的布刷成同一颜色.

这样一来，每次操作都使得集合的大小减一. 所以总次数固定是N-1.

对于每一次操作，选择最小的两张布染色一定是最小花费. 而每次的最小花费和就是总的最小花费.

维护一个优先队列，把所有大小都加进去并升序排列.

每次弹出最小的两个元素，计数并把和再push进去参与比较.

代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #define LL long long#define eps 1e-8#define maxn 101000#define mod 100000007#define inf 0x3f3f3f3f#define mid(a,b) ((a+b)>>1)#define IN freopen("in.txt","r",stdin);using namespace std;priority_queue
               
                , greater
                
                  > pq;int main(int argc, char const *argv[]){ //IN; int t; cin >> t; while(t--) { int n; scanf("%d", &n); while(!pq.empty()) pq.pop(); for(int i=1; i<=n; i++) { LL x; scanf("%lld", &x); pq.push(x); } LL ans = 0; while(pq.size() >= 2) { LL cur = pq.top(); pq.pop(); cur += pq.top(); pq.pop(); ans += cur; pq.push(cur); } printf("%lld\n", ans); } return 0;}