평일 (일상 퀴즈 - 욕심)
7813 단어 욕심
[제목 설명] 톰 은 내일 부터 주어진 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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HPU - ACM 여름 훈련 2 주차 14 급 개인전: Problem D [욕심]Problem D Problem Description 그 러 고 보 니 해동 그룹 이 안팎 으로 어려움 을 겪 고 있 고 회사 의 원로 도 XHD 부부 만 남 았 다 고 한다.분명히 여러 해 동안 싸 운 상인 으로서...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.