51Nod 1521 一维战舰

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1521

思路：
先计算出一开始最多能放多少艘战舰，然后每次输入一个点后，找到所在区间，计算出插入这个点后减少的可放战舰数量。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<stack>
 7 #include<queue>
 8 #include<cmath>
 9 using namespace std;
10 
11 const int maxn=2*1e5+5;
12 
13 int n,k,a;
14 int c[maxn];
15 
16 int main()
17 {
18     //freopen("D:\input.txt","r",stdin);
19     while(~scanf("%d%d%d",&n,&k,&a))
20     {
21         memset(c,0,sizeof(c));
22         int max_k=(n+1)/(a+1);
23         int m;
24         scanf("%d",&m);
25         int ans=-1;
26         for(int i=1;i<=m;i++)
27         {
28             int x;
29             scanf("%d",&x);
30             if(ans!=-1)  continue;
31             c[x]=1;
32             int left=x-1,right=x+1;
33             while(left>=1 && c[left]==0)      left--;
34             while(right<=n && c[right]==0)    right++;
35             max_k-=((right-left)/(a+1)-(right-x)/(a+1)-(x-left)/(a+1));
36             if(ans==-1 && max_k<k)
37                 ans=i;
38         }
39         printf("%d
",ans);
40     }
41     return 0;
42 }