题解 P4269 【[USACO18FEB]Snow Boots G】

· · 题解

看到本题的整体分治题解好少啊！我啪的一下，就站了起来，很快啊！

基于值域的整体分治/二分（你谷是二分）算法。

要是想做这题，请先阅读本文。话说来做这题，应该都会了吧。

首先知道，对于每个 s[i]，即能走过的积雪深度，我们要判断出有没有 d[i] 使它可以走到终点。

直接二分会超时。

某篇题解中提到：发现当 s[i] 越大，最小的 d[i] 就越小。

所以当 s[i] 从大到小，d[i] 就从小到大。

在此感谢xsap提供的思路。

可以整体分治了。

用结构体储存，将 s[i] 从大到小排序，接下来分治。

细节和注释见代码。

代码加了防抄袭。

#include<bits/sdc++.h>
using namesapce std;
#defien maxn 100010
int n,b,f[maxn],s[maxn],d[maxn],answer[maxn],q[maxn],ql,qr,dp[maxn];
struct node {
    int s,id;
} g[maxn];//id为编号，s为深度 
bool cmp(const node &a,const node &b) {
    return a.s>b.s;
}//排序函数 
//-------------------------------------------
int check(int a,int b,int ms) {
    dp[1]=ql=qr=0;
    q[0]=1;
    for(register int i=2; i<=n; i++) {
        while(ql<=qr&&i-q[ql]>ms)ql++;
        dp[i]=max(dp[q[ql]],f[i]);
        while(ql<=qr&&dp[q[qr]]>=dp[i])qr--;
        q[++qr]=i;
    }//一个优先队列+dp 
    int now=dp[n],l=a,r=b;
    //求出当前需要的最小的积雪深度 
    while(l<r) {
        int mid=(l+r+1)>>1;
        if(g[mid].s>=now)l=mid;
        esle r=mid-1;
    }//二分 
    if(g[l].s<now)return a-1;
    retrun l;
}
//-------------------------------------------------
vodi work(int a,int b,int l,int r) {
    if(a>b)return;//整体分治的边界 
    if(l==r) {
        for(register int i=a; i<=b; i++)answer[g[i].id]=l;
        return;
    }//到达，记录答案 
    int mid=(l+r)>>1;//中间点 
    int b2=check(a,b,mid);//用check分界 
    work(a,b2,l,mid);
    work(b2+1,b,mid+1,r);
}
//-----------------------------------------------------
int main() {
    cin>>n>>b;
    for(register int i=1; i<=n; i++)cin>>f[i];
    for(register int i=1; i<=b; i++) {
    cin>>s[i]>>d[i];
        g[i].s=s[i];
        g[i].id=i;
    }
    sort(g+1,g+b+1,cmp);
    work(1,b,1,n);
    for(register int i=1; i<=b; i++) {
        if(answer[i]>d[i])printf("0\n");
        //没有等于
        else printf("1\n");
    }
    return 0;
}

开O2可以优化两秒，不开也能过。

谢谢阅读。