Legend
Link \(\textrm{to Codeforces}\)。
给定长度 \(n\ (1 \le n \le 5000)\) 的自然数数组,你每次可以进行如下操作:
- 给一个区间的数 -1,前提是这个区间没有 0;
- 给某一个位置上的数减去任意正整数,但操作后值不能小于 0。
求出使得所有数字变成 0 的最少操作次数。
Editorial
不是很理解为什么 \(O(n)\) 的题目要出成 \(n=5000\)。
如果只有操作 \(1\),那么就是铺设道路/积木大赛。不过根据这两个经典题我们可以知道:如果要用操作 \(1\),一定会贪心地把一个数字减成 \(0\)。
那么这个不幸被减成 \(0\) 的数字是什么呢?显然是区间最小值。
\(O(n^2)\) 做法呼之欲出:每次要么区间全部都用操作 2 干掉,要么先把最小值减掉递归成若干个子区间。
用可以区间查询最小值的数据结构随便维护维护就可以做到 \(O(n \log n)\) 了。
而这个维护最小值的数据结构也可以是笛卡尔树,它正好是区间分裂的位置,方便统计区间大小和递归左右子树,可以 \(O(n)\) 解决这个问题。
Code
为了写这个题口糊了一下怎么写笛卡尔树,没想到竟然是对的(
#include <bits/stdc++.h>
using namespace std;
int read(){
char k = getchar(); int x = 0;
while(k < '0' || k > '9') k = getchar();
while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
return x;
}
const int MX = 5000 + 23;
int a[MX] ,ch[MX][2];
stack<int> stk;
int size[MX];
int dapai(int x ,int f){
if(x == 0) return 0;
int l = dapai(ch[x][0] ,x) ,r = dapai(ch[x][1] ,x);
size[x] = 1 + size[ch[x][0]] + size[ch[x][1]];
int Ans = min(l + r + a[x] - a[f] ,size[x]);
return Ans;
}
int main(){
int n = read();
for(int i = 1 ; i <= n ; ++i){
a[i] = read();
if(stk.empty() || a[stk.top()] < a[i]){
stk.push(i);
}else{
int las = 0;
while(!stk.empty() && a[stk.top()] >= a[i]){
las = stk.top(); stk.pop();
if(!stk.empty() && a[stk.top()] >= a[i]){
ch[stk.top()][1] = las;
}
}
ch[i][0] = las;
stk.push(i);
}
}
int root = 0;
while(!stk.empty()){
root = stk.top();
stk.pop();
if(!stk.empty()){
ch[stk.top()][1] = root;
}
}
cout << dapai(root ,0) << endl;
return 0;
}