[Usaco2006 Nov]Fence Repair 切割木板 Bzoj1724

这题就相当于：求把n块给定的木板合并成一个大木板所需的最少花费。

因为n<=20000，nlogn的算法可以轻松过。维护一个堆来保存每块木板的长度。每次从堆中取出前两个，将这两个合并，再放入堆中。如此反复，直至堆中只有一个元素。

其实这题就是NOIP的合并果子……只要把数据范围改下，直接交上去都能AC…… 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

/**************************************************************
    Problem: 1724
    User: abcdabcd987
    Language: C++
    Result: Accepted
    Time:24 ms
    Memory:1532 kb
****************************************************************/

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int n;
vector<int> a;

int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 0, x; i < n; ++i) {
    cin >> x;
    a.push_back(x);
  }
  make_heap(a.begin(), a.end(), greater<int>());

  long long result = 0;
  for (int i = 1; i < n; ++i) {
    int tmp = a.front();
    pop_heap(a.begin(), a.end(), greater<int>());
    a.pop_back();

    tmp += a.front();
    pop_heap(a.begin(), a.end(), greater<int>());
    a.pop_back();

    a.push_back(tmp);
    push_heap(a.begin(), a.end(), greater<int>());

    result += tmp;
  }
  cout << result;
}

Comments