ABC161 E - Yutori

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;
}
全部评论

相关推荐

程序员小白条:主要没亮点,项目也是网上的,平平无奇,那只能海投了,奖项总得有一些,然后就是现在最好是前后端都会,自己能做项目并且运维的,要么找星球项目改改,要么找个开源项目改改,自己能拓展功能才是主要的,跟做效率很低很低
点赞 评论 收藏
分享
绝迹的星:前端和后端写两份简历, 如果想干全栈就直接写求职意向为全栈工程师
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务