题目地址：http://vjudge.net/problem/UVALive-3716
和LA4726 一样，前缀和保存1~i个的不同的数量
于是得到 点p（i,sum(i)）,ans=min{k=((sum(j)-sum(i-1))/(j-i)|k满足题意 }
那么就是对于每个点t，扫描它之前的点，找出一个 斜率最小且满足题意的点
还可以再优化，下凸点在后面是没用的，应该舍掉
答案也是随着t增大，答案也会增大
然而 因为 斜率>p的是没有用的 ，所以一个点 一开始可能没用，后面可能就有用了，没法判断 是否应该舍弃这个点
看题解：
首先明确条件是(i-j)*p>=(sum[i]-sum[j])*100 => i*p-sum[i]*100 >= j*p-sum[j]*100,
sum[i]表示前i个的不相等的个数,然后就是构造一个单调递减队列，储存结果,然后二分找出最小的j，第一个入队列的是一定是<0,否则就是目前为止整个都可以
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(int)(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(int)(b);--i)
const int maxn=150000+5;
char s1[maxn],s2[maxn];
int sum[maxn],idx[maxn];
vector<int> Q;
int main(int argc, char const *argv[])
{int n,p;while(scanf("%d%d",&n,&p)==2 &&n+p){scanf("%s%s",s1+1,s2+1);Q.clear(); Q.push_back(0);idx[0]=0; sum[0]=0;int ans=0;REP(t,1,n){sum[t]=sum[t-1]+(s1[t]!=s2[t]);if(t*p-sum[t]*100 < Q[Q.size()-1]) { Q.push_back(t*p-sum[t]*100);idx[Q.size()-1]=t;}int L=0,R=Q.size()-1;int temp=t*p-sum[t]*100;while(L<R){int mid=(L+R)>>1;if(temp>=Q[mid]) R=mid;else L=mid+1;}ans=max(ans,t-idx[L]);}if(ans) printf("%d\n", ans);else printf("No solution.\n");}return 0;
}