2020.10.03日常总结——二分算法（下）

在昨天的博客中，我们粗谈了一下二分和一些零碎算法的结合，今天我们讲讲二分和 OI 中另一类非常重要的算法——dp 的结合。

$\text{最小间隔}$

$\text{[Problem]}$

现有$n$ 个数 $a_{1\cdots n}$，你需要从中选取若干个（包括 $1$ 个），要求如下：

选取的数和 $\le m$（$m$ 为题目给定的数）。 最大间隔最小（间隔：选取数列中后一个数和前一个数在原数列中位置的差 $-1$，第一个数的间隔则为它在原数列位置 $-1$；最大间隔：所有间隔的最大值）。

求可能的最小的最大间隔。

$1\le n\le 5\times 10^4,1\le m\le 1\times 10^9$。

$\text{[Solution]}$

最大值最小，一看就想到二分答案。

二分答案 $\text{mid}$，表示最大间隔为 $\text{mid}$，看看是否可行。

设计一个 dp：记 $f_i$ 表示第 $i$ 个数必选时最小的权值和。

我们有如下的转移：

$$f_i=\underset{i-\text{mid}-1\le j\le i}{\min }\left\{f_j\right\}+a_i$$

直接转移是 $O(n^2)$ 的，必超时。仔细观察可以发现，我们可以用单调队列优化我们的 dp，于是 dp 时间复杂度降为 $O(n)$。

总时间复杂度：$O(n\times \log m)$。

$\text{[code]}$

const int N=5e4+100; int l,r,mid,ans,n,T; int f[N],q[N],h,t,a[N]; inline bool check(int mid){ h=1;t=1;q[1]=f[1]=0;//init // 注意t必须初始化为1而不是0！！ for(int i=1;i<=n;i++){ while (h<=t&&q[h]+mid+1<i) ++h; f[i]=f[q[h]]+a[i];//转移方程 while (h<=t&&f[q[t]]>=f[i]) t--; q[++t]=i;//注意入队的是下标而非数 } for(int i=n-mid;i<=n;i++) if (f[i]<=T) return true; return false; } int main(){ l=1;r=n=read();T=read(); for(int i=1;i<=n;i++) a[i]=read(); while (l<=r){ mid=(l+r)>>1; if (check(mid)){ ans=mid; r=mid-1; } else l=mid+1; } printf("%d",ans); return 0; }

$\text{攻击法坛}$

$\text{[Problem]}$

一条直线上有 $n$ 个法坛，分别位于位置 $a_1,a_2,a_3\cdots a_n$，你需要把它们全部摧毁。你有两根法杖：一根可以摧毁连续 $L$ 个位置上的所有法坛，能使用 $R$ 次，另一根能摧毁连续 $2\times L$ 个位置上的所有法坛，能使用 $G$ 次。$L$ 是自己的指定的参数。求 $L$ 的最小取值使你能把 $n$ 个法坛全部摧毁。$1\le n\le 2000,1\le R,G,a_i\le 1\times 10^9(1\le i\le n)$。

$\text{[Solution]}$

首先明确一点：当 $R+G\ge n$ 时，答案为 $1$，因为我们可以对于每个法坛都用一次法杖。

明确这点有什么用？有。一特判，二把 $R,G$ 的范围降到 $1\le R,G\le n$。

答案明显有单调性（可二分性），考虑二分答案。

二分答案 $\text{mid}$ 表示判断当 $L=\text{mid}$ 时是否可行。

记 $P_i$ 表示在 $a_i$ 位置使用一次第一根法杖最远可以覆盖到哪个法坛，同理 $Q_i$ 表示在 $a_i$ 位置使用一次第二根法杖最远可以覆盖到哪个法坛。对是否熟悉的同学一读这段话应该就可以知道：我们可以用尺取法在 $O(n)$ 的时间复杂度内求出 $P_i,Q_i$。

特别地，为了方便处理，我们令 $P_{n+1}=Q_{n+1}=n$。

记 $f_{i,j}$ 表示使用 $i$ 次第一根法杖和 $j$ 次第二根法杖最多可以覆盖到前几个法坛，则有转移方程：

$$f_{i,j}=\max (P_{f_{i-1,j}+1},Q_{f_{i,j-1}+1})$$

转移方程相当的简单易懂。

初始对于 $\forall i,j$，都有 $f_{i,j}=0$ 。最后如果 $f_{R,G}=n$ 则 $\text{mid}$ 可行，否则不可行。

时间复杂度：$O(R\times G\times \log a_i)$。

$\text{[code]}$

int R,G,n,a[2010],l,r,ans,mid; int f[2010][2010],P[2010],Q[2010]; inline void ckmax(int &a,int b){ a=max(a,b);//让a取到a,b间较大值 } inline bool check(int mid){ memset(f,0,sizeof(f)); memset(P,0,sizeof(P)); memset(Q,0,sizeof(Q)); for(int i=1,j=1,k=1;i<=n;i++){ while (j<=n&&a[j]-a[i]+1<=mid) j++; while (k<=n&&a[k]-a[i]+1<=2*mid) k++; P[i]=j-1;Q[i]=k-1;//注意这里的减1 } P[n+1]=Q[n+1]=n;//特判 for(int i=0;i<=R;i++) for(int j=0;j<=G;j++){ if (i>0) ckmax(f[i][j],P[f[i-1][j]+1]); if (j>0) ckmax(f[i][j],Q[f[i][j-1]+1]); } return f[R][G]>=n; } int main(){ scanf("%d%d%d",&n,&R,&G); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1);//先要排序 if (R+G>=n){//足够各个位置都用 printf("1");return 0; } l=1;r=a[n]-a[1]+1; while (l<=r){ mid=(l+r)>>1; if (check(mid)){ ans=mid; r=mid-1; } else l=mid+1; } printf("%d",ans); return 0; }