一个字符串游戏

https://ac.nowcoder.com/acm/contest/318/I

C++版本一

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>
#define maxn 150010
struct Node {
    int sum, id;
} node[maxn];

int cmp(const void *a, const void *b) {
    struct Node *c=(Node *)a;
    struct Node *d=(Node *)b;
    if (c->sum == d->sum)
        return d->id - c->id;
    return c->sum - d->sum;
}
int max(int a,int b){
    return a>b?a:b;
}
int min(int a,int b){
    return a<b?a:b;
}

int main(void) {
    int p;
    char s1[maxn], s2[maxn];
    while (scanf("%d", &p)!=EOF) {
        scanf("%s%s", s1, s2);
        int n = strlen(s1);
        node[0].sum = 0, node[0].id = 0;
        for (int i = 0; i < n; i++) {
            if (s1[i] != s2[i])
                node[i + 1].sum = node[i].sum + 1;
            else
                node[i + 1].sum = node[i].sum;
        }
        for (int i = 1; i <= n; i++) {
            node[i].sum = node[i].sum * 100 - p * i;
            node[i].id = i;
        }
        qsort(node, n+1,sizeof(Node),cmp);
        int ans = 0, temp = n + 10;
        for (int i = n; i >= 0; i--) {
            if (node[i].id > temp)
                ans = max(ans, node[i].id - temp);
            else
                temp = min(temp, node[i].id);
        }
        printf("%d\n", ans);
    }
    return 0;
}

C++版本二 

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
typedef __int128 lll;
const int N=151000;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
char a[N],b[N];
int pre[N];
string s1,s2;
int p;
int Find(int len)
{
    if(len==0)return 1;
    for (int i = 0; i+len-1 < s1.size() ; ++i) {
        int l=i-1,r=i+len-1;
        if(l<0)
        {
            if(pre[r]*100<=p*len)return 1;
        }
        else
        {
            if((pre[r]-pre[l])*100<=p*len)return 1;
        }
    }
    return 0;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    cin>>p>>s1>>s2;
    if(s1[0]!=s2[0])pre[0]=1;
    for (int i = 1; i < s1.size(); ++i) {
        pre[i]=pre[i-1];
        if(s1[i]!=s2[i])pre[i]++;
    }
    if(p==0&&pre[s1.size()]==s1.size())
    {
        printf("0\n");
        return 0;
    }
    else if(pre[s1.size()]==s1.size()-1)
    {
        printf("1\n");
        return 0;
    }
    int l=0;
    int r=s1.size();
    int ans=0;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(Find(mid))
        {
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    l=min(r,l);
    r=s1.size();
    int cnt=0;
    while(l<r)
    {
        int mid=rand()*clock()%(r-l+1)+l;
        if(Find(mid))
        {
            ans=mid;
            l=mid+1;
        }
        cnt++;
        if(cnt>=20000)break;
    }
    printf("%d\n",ans);
    //cout << "Hello world!" << endl;
    return 0;
}