原题：NOIP2013D1T1 积木大赛
思路：玄学瞎搞
将每块区域插入一个小根堆，这里的小根堆用优先队列实现，即运用一个 \(pair\) ， \(first\) 为 \(-d_i\) ， \(second\) 为 \(i\)
每次取出堆顶，与上一次取出的数作差得到 \(d\) （如果是第一个数则上一个数为0）， \(d\) 即为从上一个深度还需向下多深到现在的深度
而这部分所需的天数为 \(d×num\) ， \(num\) 为这部分深度被分成了多少个部分，即填充1层所需的天数
开始时 \(num\) 为1，初始化一个bool数组 \(v\) 为 \(false\) ， \(v_0=v_{n+1}=true\)
每次取出堆顶的 \(second\) 即为一个分割点， \(v_{second}=true\)
此时有三种情况：
若 \(v_{second-1}==true\) 且 \(v_{second+1}==true\) ，则 \(num--\) ；
若 \(v_{second-1}==false\) 且 \(v_{second+1}==false\) ，则 \(num++\) ；
否则， \(num\) 不变。
总时间复杂度为 \(O(n\ log\ n)\)
考场AC代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100006;
int n, d[N];
bool v[N];
ll ans = 0;
priority_queue<pair<int, int> > pq;
int main() {
//freopen("road.in", "r", stdin);
//freopen("road.out", "w", stdout);
scanf("%d", &n);
while (pq.size()) pq.pop();
for (int i = 1; i <= n; i++) {
scanf("%d", &d[i]);
pq.push(make_pair(-d[i], i));
}
int num = 1, k = 0;
memset(v, 0, sizeof(v));
v[0] = v[n+1] = 1;
while (pq.size()) {
int x = pq.top().second;
pq.pop();
ans += (ll)(d[x] - k) * num;
k = d[x];
v[x] = 1;
if (v[x+1] && v[x-1]) num--;
else if (!v[x+1] && !v[x-1]) num++;
}
printf("%lld\n", ans);
return 0;
}
PS：好像没看到跟我相同做法的......
