Thallium54

AtCoder Beginner Contest 161E - Yutori 题解

贪心 题解

妙啊！

题解 #

我们可以构造一个数组LL使得第xx个工作日不早于第LxL_x天，通过从前往后尽可能早的选择工作日。同样地，我们可以构造RR数组使得第xx个工作日不晚于RxR_x天，通过从后往前选择。他必须在第ii天工作当且仅当存在xx使得Lx=Rx=iL_x=R_x=i。可以在O(N)O(N)的时间内解决。

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i <= int(r); ++i)
#define ford(i, n) for (int i = int(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int n,k,c;
    cin>>n>>k>>c;
    string s;
    cin>>s;
    vector<int> a,b;
    forn(i,n){
        if(s[i]=='o'){
            a.pb(i);
            i+=c;
        }
    }
    ford(i,n){
        if(s[i]=='o'){
            b.pb(i);
            i-=c;
        }
    }
    forn(i,k){
        if(a[i]==b[k-i-1]) cout<<a[i]+1<<endl;
    }
 
    return 0;
}