fork download
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. int n, k;
  6. int psum[100005];
  7.  
  8. bool check(int d) { // kiểm tra độ dài d có hợp lệ ko
  9. for(int i = 1; i + d - 1 <= n; ++ i) {
  10. int cnt = psum[i + d - 1] - psum[i - 1];
  11. if(cnt < k) return false;
  12. }
  13. return true;
  14. }
  15.  
  16. int32_t main() {
  17. cin >> n >> k;
  18. string s; cin >> s;
  19. for(int i = 1; i <= n; ++ i) { // tính mảng cộng dồn để đếm số cây trong đoạn
  20. psum[i] = psum[i - 1];
  21. if(s[i - 1] == '#') ++ psum[i];
  22. }
  23.  
  24. int l = 1, r = n, d = -1;
  25. while(l <= r) { // tìm d bằng tìm kiếm nhị phân
  26. int mid = (l + r) / 2;
  27. if(check(mid)) {
  28. d = mid;
  29. r = mid - 1;
  30. }
  31. else l = mid + 1;
  32. }
  33. cout << d;
  34. }
Success #stdin #stdout 0.01s 5288KB
stdin
Standard input is empty
stdout
-1