头条9.10笔试附加题( 讲解+代码)

帮同学做的。。。

前两个题挺简单的，第2题，有个无覆盖的条件感觉一点用没有，直接2分upper_bound - lower_bound过的

这题挺难的，是我做笔试最难的题了，但原理不难，二分答案+O(n)验证，难点是中间有一个推公式的步骤

首先 存下a-z 的字母的下标，26个vector

然后二分答案，因为长度L的可以凑出来，L-1的也一定可以凑出来

验证的时候，验证26个字母，存在一个满足要求就ok了

关键是如何对每个字母验证，假设为验证长度K，对字母a

首先字母a要大于等于K个

然后依次验证第1到K个a是否可以用m次交换连起来，第2到K+1个a是否, 第3到K+2个a， 原则是所有K个a往中间那个a靠近，如果K是偶数，中间的2个a，随便哪个都行，理解是这么理解，但实现时候如果暴力实现是要超时的，我是用累加和，验证的，具体看代码，这个地方看懂了这道题就ok了。

#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
const int N=3e5+9;
#define ll long long
vector<int> a[26];
int m;
bool check(int l)
{
    if(l==1) return 1;
    for(int i=0;i<26;i++)
    if(a[i].size()>=l)
    {
        for(int j=l-1;j<a[i].size();j++)
        {
            int dis=l/2;
            int pos=j-l+1+dis;
            int mid=a[i][pos];
            if(pos-1>=0) mid-=a[i][j-l+1+dis-1];
            int sum_left=0;
            if(pos-1>=0) sum_left=a[i][pos-1];
            if(pos-dis-1>=0) sum_left-=a[i][pos-dis-1];

            int sum_right=a[i][j];
            if(pos-1>=0) sum_right-=a[i][pos-1];

            int left=mid*dis-dis*(dis+1)/2;
            int tt=l-dis;
            int right=mid*tt+tt*(tt-1)/2;

            int cost=left-sum_left+sum_right-right;
            if(cost<=m) return 1;
        }
    }
    return 0;
}
int main()
{
    string s;cin>>s>>m;
    //for(int i=0;i<26;i++) a[i].push_back(0);
    for(int i=0;s[i];i++)
    {
        a[s[i]-'a'].push_back(i);
    }
    for(int i=0;i<26;i++)
    {
        for(int j=1;j<a[i].size();j++)
            a[i][j]+=a[i][j-1];
    }
    int _s=1,_t=s.length();
    while(_s<=_t)
    {
        int mid=(_s+_t)>>1;
        if(check(mid)) _s=mid+1;
        else _t=mid-1;
    }
    cout<<_t<<endl;

    return 0;
}