题解：AT_abc203_f [ABC203F] Weed

· · 题解

首先看到 2 \times 10^5 的数据范围猜想是贪心，但是手玩了一下样例发现似乎并没有什么特点。但仍考虑到每次选择的草的高度一定单调递减，于是先对数组进行排序。

接下来考虑 dp。我们考察每次拔除草的过程，就是每次将大于原最大值的部分除去。这个过程最多只会进行 \log_2V，（V 为值域）次，因为每次操作后的最大值一定小于等于操作前最大值的一半。于是猜测 dp 状态中大概有这一项。

后面的步骤就顺理成章了，定义 dp_{i,j} 为前 i 个数高桥操作 j 次的最小青木操作次数。边界为 dp_{0,0}=1，统计答案为找到第一个 i,使得 dp_{n,i}\le k。同时有转移：

dp_{i,j}=\min(dp_{i-1,j}+1,\min_{\frac{a_i}{2}<a_k,k<i}\{dp_{k,j-1}\})

这个转移是 O(n) 的，不够快。但是发现由第一个满足条件的 k 之后的状态转移来一定是不优的。可以使用双指针或二分找到第一个可转移点，由它转移即可。
复杂度 O(n\log n +n\log V)，V 为值域。

代码：

#include<bits/stdc++.h>
#define int long long
#define maxn 200005
using namespace std;
int n,k;
int a[maxn],dp[maxn][50];
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    memset(dp,0x3f,sizeof dp);
    sort(a+1,a+n+1);
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=40;j++){
            dp[i][j]=dp[i-1][j]+1;
            int last=upper_bound(a+1,a+i+1,a[i]/2)-a-1;
            if(j>0)dp[i][j]=min(dp[i][j],dp[last][j-1]);
        }
    }
    for(int i=0;i<=40;i++){
        if(dp[n][i]<=k){
            cout<<i<<' '<<dp[n][i];
            break;
        }
    }
    return 0;
}