ABC161 E - Yutori

题意

给你一个长度为n的字符串s（仅由’x’和’o’组成），要求你选出k个’o’且满足两个’o’中间相隔至少c个字符。
输出无论怎么选一定要选的位置。

思路

贪心
正序遍历贪心求最小位置记录在数组a中，倒序遍历贪心求最大位置记录在数组b中，当a[i]+b[i]=k+1的时候，无论何种方法选择到第k个选择时两种方法都会选到这个位置，输出这个位置。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 2e5 + 5;int n,k,c,a[N],b[N];
string s;int main(){ios::sync_with_stdio(false);cin.tie(0);cin>>n>>k>>c>>s;int cnt=0;for(int i=0;i<s.size()&&cnt<k;i++){if(s[i]=='o'){cnt++;a[i]=cnt;i+=c;}}cnt=0;for(int i=s.size()-1;i>=0&&cnt<k;i--){if(s[i]=='o'){cnt++;b[i]=cnt;i-=c;}}for(int i=0;i<s.size();i++){if(a[i]!=0&&b[i]!=0&&a[i]+b[i]==k+1) cout<<i+1<<'\n';}return 0;
}