题目描述
算法
(DP) $O(n\log \max(a_i))$
先对杂草按高度降序排列。
然后考虑 DP
:
$dp[i][j]$:对于给定的前 $i$ 颗杂草,青木最少需要拔掉多少杂草高桥才能在 $j$ 次操作内拔完这些杂草。
注意到高桥的最大操作次数是 $\lfloor \log \max(a_i) \rfloor + 1$,所以 $0 \leqslant j \leqslant 30$
若青木拔掉第 $i$ 颗草:
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
若青木不拔掉第 $i$ 颗草:
dp[r][j + 1] = min(dp[r][j + 1], dp[i][j]); // r 表示大于 a[i]/2 的最大下标
初始条件:
dp[0][0] = 0;
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
const int M = 31;
const int INF = 1001001001;
int dp[200005][M + 1];
bool chmin(int& x, int y) {
if (x > y) { x = y; return true; }
return false;
}
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
rep(i, n) cin >> a[i];
sort(a.rbegin(), a.rend());
rep(i, n + 1)rep(j, M) dp[i][j] = INF;
dp[0][0] = 0;
int r = 0;
rep(i, n) {
while (r < n and a[r] * 2 > a[i]) ++r;
rep(j, M) {
chmin(dp[i + 1][j], dp[i][j] + 1);
chmin(dp[r][j + 1], dp[i][j]);
}
}
rep(j, M) {
if (dp[n][j] <= k) {
cout << j << " " << dp[n][j] << '\n';
return 0;
}
}
assert(false);
return 0;
}