UPC-Longest X

UPC个人训练赛21

题目描述

Given is a string S consisting of X and ..

You can do the following operation on S between 0 and K times (inclusive).

Replace a . with an X.
What is the maximum possible number of consecutive Xs in S after the operations?

Constraints
1≤∣S∣≤2×105
Each character of S is X or ..
0≤K≤2×105
K is an integer.

输入

Input is given from Standard Input in the following format:

S
K

输出

Print the answer.

输入：

【样例1】
XX...X.X.X.
2
【样例2】
XXXX
200000

输出：

【样例1】
5
【样例2】
4

题目大意：

给定一个由X和.组成的字符串s，可以进行K次操作将字符串中的.变为X，问最多可以有多少个连续的X

思路：

这个题目可以考虑使用一个指针，从当前的第i个往后指，知道指针超出字符串或者已经有k个点了，然后每次判断区间的最大，最终输出这个最大的长度。

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    string s;
    int k;
    int cnt = 0;
    int ans = 0;
    int r = 0;
    cin >>s >> k;
    int len = s.size();
    for(int i = 0;i < len;i++){
        while(r < len&&s[r]== 'X'||(s[r] == '.' && cnt+1<=k)){
            if(s[r] == '.')
                cnt++;
            r++;
        }
        ans = max(ans,r-i);
        if(s[i] == '.')
            cnt--;
    }
    cout << ans;
}