[UVALive 3716] DNA Regions

图片加载可能有点慢，请跳过题面先看题解，谢谢

对于一段合法的区间 \([j+1,i]\) ，必须满足：\(\frac{sum[i]-sum[j]}{i-j}\leq \frac{P}{100}\)
我们把式子化一下，即：\(sum[j]*100-j*p\geq sum[i]*100-i*p\)
也就是说，我们要找到一对满足这个式子的 \((i,j)\) 使得 \(i-j\) 最大
$
$
那么我这里讲两种做法
$
$
第一种：我们针对每一个位置记一个 \(S\)，\(S=sum[j]*100-j*p\)
按照 \(S\)，将所有的位置 \(sort\)（记得要把 \(0\) 也放进去），这样我们就能保证所有的 \(S\) 有序
从头到尾枚举，如果当前枚举到的这一位的原位置大于当前记录的最小位置，则更新答案，
如果当前枚举到的这一位的原位置小于当前记录的最小位置，则更新最小位置
时间复杂度：排序，\(O(nlogn)\)，统计答案，\(O(n)\)

//made by Hero_of_Someone
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define il inline
#define RG register
using namespace std;

int n,p;
char A[150040],B[150040];
struct S{int x,s;
   il bool operator<(const S &a)const{
      return s==a.s?(x<a.x):(s>a.s);
   }
}a[150040];

il void init(){
   scanf("%s%s",A,B); int cnt=0;
   for(int i=1;i<=n;i++){
      if(A[i-1]!=B[i-1]) cnt++;
      a[i].x=i,a[i].s=cnt*100-i*p;
   }
   a[0].x=a[0].s=0;sort(a,a+n+1);
}

il void work(){
   int x=a[0].x,ans=0;
   for(int i=1;i<=n;i++)
      if(a[i].x<x) x=a[i].x; 
      else ans=max(ans,a[i].x-x);
   if(!ans) puts("No solution.");
   else printf("%d\n",ans);
}

int main(){ while(scanf("%d%d",&n,&p)&&n){ init(); work(); } return 0; }

$
$
方法二：
维护一个单调队列（其实只是一个数组），使得队列中的 \(S=sum[i]*100-i*p\) 保持递增
如果当前位的 \(S\) 值大于队尾，则插入该 \(S\)
否则在队列中二分，查找到一个最小 \(j\)，使得 \(S[j]\geq S[i]\)，更新答案
时间复杂度：\(O(nlogn)\) （比 \(sort\) 要优秀）

//made by Hero_of_Someone
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define N (150040)
#define il inline
#define RG register
using namespace std;
il int gi(){ RG int x=0,q=1; RG char ch=getchar(); while( ( ch<'0' || ch>'9' ) && ch!='-' ) ch=getchar();
  if( ch=='-' ) q=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x; }

char A[N],B[N];
int n,p,sum[N],id[N];
int que[N];

il void work(){
   scanf("%s%s",A+1,B+1);
   int cnt=0,tl=0,ans=0;
   for(int i=1;i<=n;i++){
      cnt+=(A[i]!=B[i]);
      RG int t=cnt*100-i*p;
      if(t>que[tl]){ 
         que[++tl]=t,id[tl]=i;
         continue;
      }
      RG int l=0,r=tl;
      while(l<=r){
         RG int mid=(l+r)>>1;
         if(que[mid]<t) l=mid+1;
         else r=mid-1;
      }
      ans=max(ans,i-id[l]);
   }
   if(!ans) puts("No solution.");
   else printf("%d\n",ans);
}

int main(){ while(scanf("%d%d",&n,&p)&&n) work(); return 0; }