重基础系列\(1\)

思想

用 \(O(\log n)\) 的复杂度在具有单调性的区间 \([L,R]\)内查找一个最优答案。

例题

1.P1314 NOIP2011 提高组 聪明的质监员

前缀和数组 \(sumap(i)\) 和 \(sumw(i)\) 维护当前 \(W\) 对应的 \(y_i\) 值，也就是：

\[\begin{cases}sumap(i)=\sum_{j=1}^{i}[w_j\ge W]\\sumw(i)=\sum_{j=1}^{i}[w_j\ge W]v_j \end{cases} \]

对于 \([L,R]\) 区间的值设为 \(ans\)，

\[ans=(sumap(R)-sumap(L-1))\times(sumw(R)-sumw(L-1)) \]

用该方法判断即可。

inline bool check(ll w){
    sum_ap[0]=sum_v[0]=0LL;
    ll sum=0;
    for(int i=1;i<=n;i++){
        if(a[i].w>=w){
            sum_ap[i]=sum_ap[i-1]+1LL;
            sum_v[i]=sum_v[i-1]+(ll)a[i].v;
        }
        else{
            sum_ap[i]=sum_ap[i-1];
            sum_v[i]=sum_v[i-1];
        }
    }
    for(int i=1;i<=m;i++){
        ll l=q[i].l,r=q[i].r;
        sum=sum+(sum_ap[r]-sum_ap[l-1])*(sum_v[r]-sum_v[l-1]);
    }
    ans=llabs(sum-s);
    return sum>s;
}
int main(){
    n=read(),m=read(),s=read();
    ll l=0x3f3f3f3f3f3f3f3f,r=-1;
    for(int i=1;i<=n;i++){
        a[i].w=read(),a[i].v=read();
        l=min(l,a[i].w),r=max(r,a[i].w);
    }
    for(int i=1;i<=m;i++){
        q[i].l=read(),q[i].r=read();
    }
    while(l<=r){
        ll mid=(l+r)>>1;
        if(check(mid)){
            l=mid+1;
        }
        else{
            r=mid-1;
        }
        ansx=min(ans,ansx);
    }
    printf("%lld",ansx);
    return 0;
}

2.P1182 数列分段 Section II / P2884 USACO07MAR Monthly Expense S

只需判断当前区间和最大值为 \(mid\) 时，是否满足 \(m\) 段的条件。

判断时当目前的段数大于 \(m\) 时，说明此时的 \(mid\) 是不可行的，向右缩短区间，即 \(l=mid+1\)；反之说明此时的 \(mid\) 可能是最后的答案，向左缩短区间并且不能不包括当前 \(mid\) ，即 \(r=mid\)，因为在可行解范围前的一个操作一定是由不可行的向右缩小转换而来的，而这里的 \(l\) 就恰好记录了该区间的最小值，所以最后输出 \(l\)。

总而言之，求最大值的最小值，大概率输出左边界。

3.P2329 SCOI2005 栅栏

题解

4.P2218 HAOI 2007 覆盖问题

为了最大化利用这 \(3\) 个 \(l\times l\) 的正方形，一定是要把正方形的一个角放在当前点集中的四个角位置，所以三次搜索加上判断当前长度是否能把剩余点覆盖，二分即可。

5.P2511 HAOI 2008 木棍分割

第一个结果非常好做，二分判断是否符合 \(m+1\) 即可。注意是切割 \(m\) 次，也就是切成了 \(m+1\) 段

对于第二个结果，考虑动态规划，令 \(dp(i,j)\) 表示前 \(i\) 个数分成 \(j\) 组的情况数，维护一个前缀和 \(sum()\) ，可以得到：

\[dp(i,j)=\sum_{k=0}^{i-1}dp(k,j-1) [sum(i)-sum(k)\leq ans] \]

而最终答案为 \(\sum_{j=0}^{m+1}dp(n,j)\)，显然 \(O(n^3)\) 的复杂度十分不优秀，考虑优化。

首先显然可以滚掉第二维，然后发现因为前缀和是单调递增的，也就是只需要找到满足 \(sum(i)-sum(k)\leq ans\) 的 \(k\) 的最小值，然后每次转移用\(sumdp(i)-sumdp(k-1)\) 即可。

6.P2898 Haybale Guessing G

因为题目保证每个下标对应数据的互异性，所以当存在两个区间 \(A[l_1,r_1],B[l_2,r_2]\) 且 \(A \cap B =\varnothing\) 时，一定不合法。同时如果我们将所有信息按从大到小的顺序覆盖，一旦出现 \(A \subseteq B\) 且 \(A\) 所对应最小值小于 \(B\) 所对应的最小值，一定不合法。使用并查集维护并集，并判断当前信息与上一信息的交集。以此作为判断，进行二分。