题目链接 http://codeforces.com/contest/729/problem/D
题意:给你一个1*n的区域有a艘船,每艘船宽b,已经开了k枪都没打到,问你最少再开几枪至少能打到一艘船。
想清楚了挺简单的,只要找到所有船可能放的地方然后存下再找任意sum-a+1个位置即可。
#include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int M = 2e5 + 10; char s[M]; int main() { int n , a , b , k; cin >> n >> a >> b >> k; cin >> s; vector<int>q; int len = strlen(s); for(int i = 0 ; i + b - 1 < n ; ++i) { int flag = 0; for(int j = 0 ; j < b && i < n ; ++j , ++i) { if(s[i] == '1') { flag = 1; break; } } if(!flag) { q.push_back(i - 1); i--; } } int gg = q.size() - a + 1; cout << gg << endl; for(int i = 0 ; i < gg ; i++) { cout << q[i] + 1 << ' '; } return 0; }