[Codeforces][Round #650][Div.3] C : Social Distance (C++)

https://codeforces.com/contest/1367/problem/C

Problem - C - Codeforces

[난이도] Div.3
[유형] Greedy

[풀이]
앞에서부터 사람을 앉혀보면 된다. 최대한 왼쪽에 붙도록 앉히는게 최적이다.

 

#include <string>
#include <cstdio>
using namespace std;
int tc,n,k,a[200000];
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d",&n,&k);
        int fi=n;
        for(int i=0;i<n;i++) {
            scanf("%1d",&a[i]);
            if(a[i]==1 && fi==n) fi=i;
        }
        int cnt=fi/(k+1);
        if(fi==n) {
            cnt=1+(n-1)/(k+1);
        };
        for(int i=fi;i<n;){
            int ok=1;
            int j;
            for(j=i+1;j<=i+k&&j<n;j++) {
                if(a[j]) {
                    ok=0;
                    break;
                }
            }
            cnt+=ok&&!a[i];
            i=j;
        }
        printf("%d\n",cnt);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round650-Div.3/C.cpp