http://codeforces.com/problemset/problem/248/D
题意： 有一个字符串，包含H,点和S三种字符，其中H代表人，S代表超市。你现在花了一分钟到达了最左边的点。两个点之间的移动花费一分钟。每个H需要这个糖果，每个S可以出售一个糖果。现在给出时间t，求最少的初始糖果数量，可以在规定时间内让每个H得到糖果。
解析：
显然二分初始值val，并且显然我到达一个H时如果手上有糖果就直接给他一个。
那么找到那个使糖果刚好花完的点p（使用线段树，因为值连续，所以找第一个小于等于即可），当前已经花费时间p分钟。然后求dp[p+1]表示p+1这个点开始，手上没有糖果的最少时间。
这个dp怎么处理？从后往前做。
当点为H时，我可以找到第一个刚好匹配的点，来回跑3次；也可以直接使最后一个H满足，再跑回来。 当点为S时，显然如果可以完全匹配就直接转移；还有一种情况就是S个数大于H，只要让最后一个H满足即可。3. 当点为点时，继承一下状态即可，如果dp[i+1]合法，直接dp[i]=dp[i+1]+1
完全匹配只需要找前缀和数组中，下一个pre[i-1]出现的位置即可。注意后面没有H时dp为0，S<H时为-1。
代码：
#include<bits/stdc++.h> using namespace std; #define LL long long #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) const int maxn=5e5+9; int n,t; char x[maxn]; int pre[maxn]; int nex[maxn]; int dp[maxn]; int mi[maxn<<2]; #define mid (l+r>>1) #define ls (rt<<1) #define rs (rt<<1|1) void build(int rt,int l,int r){ if(l==r)return (void)(mi[rt]=pre[l]); build(ls,l,mid); build(rs,mid+1,r); mi[rt]=min(mi[ls],mi[rs]); } int pos; void query(int rt,int l,int r,int L,int R,int val){ if(pos!=-1||mi[rt]>val)return; if(l>=L&&r<=R){ if(l==r){ pos=l; } else{ if(mi[ls]<=val)query(ls,l,mid,L,R,val); if(pos==-1&&mi[rs]<=val)query(rs,mid+1,r,L,R,val); } } if(L<=mid&&mi[ls]<=val)query(ls,l,mid,L,R,val); if(R>mid&&pos==-1&&mi[rs]<=val)query(rs,mid+1,r,L,R,val); } bool check(int val){ pos=-1; query(1,1,n,1,n,-val); if(val==0)pos=0; if(pos==-1)return 1; return dp[pos+1]+pos<=t; } int main(){ scanf("%d%d",&n,&t); scanf("%s",x+1); int SUMH=0,SUMS=0; rep(i,1,n){ if(x[i]=='H')pre[i]=-1,SUMH++; else if(x[i]=='S')pre[i]=1,SUMS++; } rep(i,1,n)pre[i]+=pre[i-1]; build(1,1,n); unordered_map<int,int>MP; unordered_map<int,int>LAST; per(i,n,0){ if(MP.count(pre[i]))nex[i]=MP[pre[i]]; MP[pre[i]]=i; if(!LAST.count(pre[i])){ LAST[pre[i]]=i; } } int H=0; //last H per(i,n,1){ if(H==0&&x[i]=='H')H=i; if(pre[n]-pre[i-1]<0){ dp[i]=-1;continue; } if(H==0){ dp[i]=0; continue; } if(x[i]=='.'){ if(dp[i+1]==-1) dp[i]=-1; else if(dp[i+1]==0) dp[i]=0; else dp[i]=dp[i+1]+1; } else if(x[i]=='S'){ int p=nex[i-1]; if(!p) dp[i]=H-i+1; else dp[i]=dp[p+1]+(p-i+1); } else { int p=nex[i-1]; if(H>p) dp[i]=dp[p+1]+3*(p-i+1)-2; else dp[i]=dp[p+1]+2*(p-i+1)-1; p=LAST[pre[i-1]]; if(pre[H]-pre[i-1]>=0)p=H; dp[i]=min(dp[i],2*(p-i+1)-1); } } if(H&&H>t){ return 0*printf("-1\n"); } int l=max(0,SUMH-SUMS),r=n,ans=n; while(l<=r){ if(check(mid))ans=mid,r=mid-1; else l=mid+1; } cout<<ans<<endl; }