本文主要是介绍CodeForces 487B Strip，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
n（10^5）个人分组 每组最少L个人 每组的差异为组中人最大价值-最小价值 要求差异均不超过S 问最少分几组
思路：
假设已经知道组的区间[l,r]那么计算差异就是简单的rmq问题 可以用线段树搞
我们可以用dp[i]表示到i位置产生的最少组数
假设从i位置开始分一组 会影响到哪些dp呢 我们可以利用二分+rmq找到这个组最远延伸到哪里 从L到最远点这个区间的dp就是受这一组影响的 那么对于一段连续的区间的值的更新 我们也可以用线段树搞
那么总复杂度就为O(n(logn)^2)
代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<vector>
using namespace std;
#define inf 1000000001
#define N 100010
#define L(x) (x<<1)
#define R(x) ((x<<1)|1)int n,cha,len,ans,MX,MN;
struct nodea{int l,r,mn,mx;
}ta[N*4];void inita(int l,int r,int i){ta[i].l=l;ta[i].r=r;if(l==r){scanf("%d",&ta[i].mn);ta[i].mx=ta[i].mn;return;}int mid=((l+r)>>1);inita(l,mid,L(i));inita(mid+1,r,R(i));ta[i].mn=min(ta[L(i)].mn,ta[R(i)].mn);ta[i].mx=max(ta[L(i)].mx,ta[R(i)].mx);
}void querya(int l,int r,int i){if(l==ta[i].l&&r==ta[i].r){MN=min(MN,ta[i].mn);MX=max(MX,ta[i].mx);return;}int mid=((ta[i].l+ta[i].r)>>1);if(r<=mid) querya(l,r,L(i));else if(l>mid) querya(l,r,R(i));else{querya(l,mid,L(i));querya(mid+1,r,R(i));}
}struct nodedp{int l,r,mn,lazy;
}tdp[N*4];void initdp(int l,int r,int i){tdp[i].l=l;tdp[i].r=r;tdp[i].lazy=inf;if(l==r){if(l) tdp[i].mn=inf;else tdp[i].mn=0;return;}int mid=((l+r)>>1);initdp(l,mid,L(i));initdp(mid+1,r,R(i));tdp[i].mn=min(tdp[L(i)].mn,tdp[R(i)].mn);
}void down(int i){if(tdp[i].lazy!=inf){tdp[L(i)].mn=min(tdp[L(i)].mn,tdp[i].lazy);tdp[R(i)].mn=min(tdp[R(i)].mn,tdp[i].lazy);tdp[L(i)].lazy=min(tdp[L(i)].lazy,tdp[i].lazy);tdp[R(i)].lazy=min(tdp[R(i)].lazy,tdp[i].lazy);tdp[i].lazy=inf;}
}void updatedp(int l,int r,int i,int key){if(tdp[i].l==l&&r==tdp[i].r){tdp[i].mn=min(tdp[i].mn,key);tdp[i].lazy=min(tdp[i].lazy,key);return;}down(i);int mid=((tdp[i].l+tdp[i].r)>>1);if(r<=mid) updatedp(l,r,L(i),key);else if(l>mid) updatedp(l,r,R(i),key);else{updatedp(l,mid,L(i),key);updatedp(mid+1,r,R(i),key);}tdp[i].mn=min(tdp[L(i)].mn,tdp[R(i)].mn);
}int querydp(int pos,int i){if(tdp[i].l==tdp[i].r){return tdp[i].mn;}down(i);int mid=((tdp[i].l+tdp[i].r)>>1);if(pos<=mid) return querydp(pos,L(i));else return querydp(pos,R(i));
}int main(){scanf("%d%d%d",&n,&cha,&len);inita(1,n,1);initdp(0,n+1,1);for(int i=1;i<=n;i++){int l=i+len-1,r=n,res=-1;while(l<=r){int mid=((l+r)>>1);MX=-inf;MN=inf;querya(i,mid,1);//printf("%d %d %d %d\n",i,mid,MX,MN);if(MX-MN<=cha){res=mid;l=mid+1;}else r=mid-1;}if(res!=-1){int dp=querydp(i-1,1);//printf("%d %d %d\n",i+len-1,res,dp+1);updatedp(i+len-1,res,1,dp+1);}}ans=querydp(n,1);if(ans==inf) ans=-1;printf("%d\n",ans);return 0;
}这篇关于CodeForces 487B Strip的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
