평일 (일상 퀴즈 - 욕심)

7813 단어 욕심
(시간 제한: 1 초 메모리 제한: 128 MB)
[제목 설명] 톰 은 내일 부터 주어진 N 일 동안 K 일 을 선택해 일 하기 로 했다.정수 C 와 문자열 S 를 지정 합 니 다. 톰 의 근무일 은 다음 과 같 습 니 다. (1) 하루 일 한 후에 그 는 다음 C 일 에 일 하지 않 을 것 입 니 다.(2) S 의 i 번 째 문자 가 x 라면 그 는 i 일 에 일 하지 않 을 것 이다.그 중 첫째 날 이 내일 이 고, 둘째 날 이 모레 인 것 으로 유추 된다.톰 이 일 해 야 할 모든 날 짜 를 프로 그래 밍 해 보 세 요.일 해 야 할 날 이 없다 면 아무것도 수출 하지 않 는 다.
【 데이터 범 위 】 1 ≤ N ≤ 2×10 5 ;1≤K≤N;0≤C≤N; N 은 S 길이 입 니 다.S 에 포 함 된 문 자 는 o 또는 x 밖 에 없습니다.
[입력 형식] 한 행위 의 세 개의 정 수 를 입력 하 십시오. 즉, N, K 와 C 입 니 다. 인접 한 두 정수 사 이 를 모두 하나의 빈 칸 으로 구분 합 니 다.두 번 째 줄 은 문자열 S 입 니 다.
[출력 형식] 톰 이 일 할 모든 날 의 번 호 를 오름차 순 으로 인쇄 합 니 다. 줄 마다 하루 입 니 다.일 해 야 할 날 이 없 으 면 아무것도 출력 하지 않 는 다 (예시 3).
[입력 샘플 1] 11, 3, 2 ooxxxxxxxoo
[출력 예시 1] 6
[사례 1 설명] 톰 은 11 일 중 3 일 을 선택 하여 일 을 하고 하루 일 한 후에 그 는 추 후 이틀 안에 일 을 멈 출 것 이다.그의 근무일 은 다음 과 같은 네 가지 가능 한 선택 이 있 기 때문이다. 첫 번 째 선택 은 첫째 날, 여섯 번 째 날, 열 번 째 날 이다.두 번 째 선택: 1 일, 6 일, 11 일;3 번 째 선택: 2 일, 6 일, 10 일 네 번 째 선택: 2 일, 6 일, 11 일.그래서 그 는 6 일 째 일 해 야 한다. 답 은 6 이다.
[샘플 입력 2] 5, 2, 3 Ooxoo
[출력 샘플 2] 1, 5.
사고의 방향
반드시 일 해 야 하 는 날 은 정반 대로 한 번 씩 스 캔 하고 근무일 을 기록 하 며 근무일 교 집합 을 구하 면 된다.
코드
#include
using namespace std;

int n,c,k;
int l[200010],r[201000];
char s[201000];

int main()
{
	//freopen("work.in","r",stdin);
	//freopen("work.out","w",stdout);
	scanf("%d%d%d",&n,&k,&c);
	scanf("%s",s);
	int cnt=k-1,mx=n;
	for(int i=strlen(s)-1;i>=0;i--)
	if(cnt>=0&&i<mx&&s[i]=='o')
	{
		r[cnt]=i;
		mx=i-c;
		cnt--;
	}
	cnt=0,mx=-1;
	for(int i=0;i<strlen(s);i++)
	if(i>mx&&s[i]=='o')
	{
		l[cnt]=i;
		mx=i+c;
		cnt++;
	}
	for(int i=0;i<k;i++)
	if(l[i]==r[i])cout<<l[i]+1<<endl;
	return 0;
}

좋은 웹페이지 즐겨찾기