UVA1392 【DNA Regions】

题目大意：给n和p，以及两个DNA序列，要求找出其中突变率不超过p%的最长子串的长度。

题解：

对于区间 [j+1,i]，必须满足：(sum[i]−sum[j])/(i−j)≤P/100才符合题意;

即：

sum[j]∗100−j∗p≥sum[i]∗100−i∗p

也就是说，我们要找到一对满足这个式子的 (i,j) 使得 i−j 最大，可以用单调队列，也可以直接排序，不过单调队列更优秀。

我这里用到的是排序。

我们针对每一个位置记一个 k（num）=sum[j]∗100−j∗p，再按照 k（num），将所有的位置的标号排序，这样我们就能保证所有的 S 有序

从头到尾枚举，如果当前枚举到的这一位的原位置大于当前记录的最小位置，则更新答案，如果当前枚举到的这一位的原位置小于当前记录的最小位置，则更新最小位置

时间复杂度：排序，O(nlogn)，统计答案，O(n)

最后附上代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct A
{
    int id,num;
}k[150001];
int sum[150001],n,p;
char s1[150001],s2[150001];
int max(int a,int b)
{
    if(a>b)
        return a;
    return b;
}
bool cmp(const A &a,const A &b)
{
    if(a.num==b.num)
        return a.id<b.id;
    return a.num>b.num;
}
int main()
{
    while(scanf("%d%d",&n,&p)!=EOF&&n!=0&&p!=0)
    {
        int cnt=0;
        memset(k,0,sizeof(k));
        scanf("%s%s",s1+1,s2+1);
        for(int i=1;i<=n;i++)
        {
            if(s1[i]!=s2[i])
                cnt++;  
            k[i].num=cnt*100-i*p;
            k[i].id=i;
        }
        k[0].id=0;
        k[0].num=0;
        sort(k,k+n+1,cmp);
        int idx=k[0].id,ans=0;
        for(int i=1;i<=n;i++)
        {
            if(k[i].id<idx)
                idx=k[i].id;
            else
                ans=max(ans,k[i].id-idx);
        }
        if(ans==0)
            printf("No solution.
");
        else
            printf("%d
",ans);
    } 
　　return 0;
}