Technocup 2017 - Elimination Round 2 D. Sea Battle

本文主要是介绍Technocup 2017 - Elimination Round 2 D. Sea Battle，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算是正式开始康复训练啦

这是一题简单的思维题…
第一想法是鸽巢原理，因为“最小数量“，“至少一个“等关键词。
那么，就要先知道鸽巢的总数，也就是可能是船的位置的数量。这个时候就要用贪心做，然后只需要保存每个船整个身位中的一个点就行。
然后用鸽巢原理输出数目和顺序就行。

#include <cstdio>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
const int maxn = 2*1e5+10;  
char str[maxn];  
int ans[maxn];  
int main()  
{  int n,a,b,k;  while(scanf("%d%d%d%d",&n,&a,&b,&k)!=EOF)  {  scanf("%s",str+1);  int m=0,cnt=0;  for(int i=1;i<=n;++i)  {  if(str[i]=='0')  {  cnt++;  if(cnt==b)  {  ans[m++]=i;  cnt=0;  }  }  if(str[i]=='1')  cnt=0;  }  printf("%d\n",m+1-a);    for(int i=0;i<m-a+1;i++)  printf("%d ",ans[i]);   printf("\n");  }  return 0;   
}   

这篇关于Technocup 2017 - Elimination Round 2 D. Sea Battle的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---