题目：51nod：
题目Codeforces:
题目注意到两个战舰不能挨在一起就可以了。
// 每一段 struct node{ int left; // 段的左端点 int right; // 段的右端点 int length; // 段长度 int ship; // 段最大容纳战舰数 }arr[200005];
每一段可容纳战舰数：
ship*a + (ship - 1) <= length; --> ship = (length+1) / (a+1);（舍去小数部分）
构造出这么一个数据结构就简单了。
现在还有一个问题：找到说miss的点所在段还需要时间，就算是二分查找也需要O(log(n))，加上遍历的O(n)，时间复杂度O(n*log(n))。
可不可能会超时呢？我认为有可能，所以保险起见，我用了一个数组index[i]表示第i个点所在的段，用空间换时间，比较值。
一次就AC了，思路就这么多，上代码把：
#include <bitsstdc++.h> using namespace std; typedef long long ll; // 每一段 struct node{ int left; // 段的左端点 int right; // 段的右端点 int length; // 段长度 int ship; // 段最大容纳战舰数 }arr[200005]; int len = 0; // 段的数量 int index[200005]; // 每一个点所处的段 int n,k,a,m; int miss; // 每一次说miss的位置。 int sumShip = 0; // 现阶段可容纳最多战舰数 // 获取某段可容纳最大战舰数量 int maxShip(node node1){ return (node1.length+1)/(a+1); } //初始化 void init(){ arr[0].left = 1;arr[0].right = n; arr[0].length = arr[0].right - arr[0].left + 1; arr[0].ship = maxShip(arr[0]); sumShip = arr[0].ship; len = 1; } //更新段 void updataNode(int miss){ int con = index[miss]; // miss位置所在段 node* x = &arr[con]; //取出这个段 int shipNum = x->ship; arr[len].left = miss+1; arr[len].right = x->right; arr[len].length = arr[len].right - arr[len].left + 1; arr[len].ship = maxShip(arr[len]); replace(index+arr[len].left,index+arr[len].right+1 , con ,len); // 将其中一部分所在段改变 x->right = miss-1; x->length = x->right - x->left + 1; x->ship = maxShip(*x); sumShip -= shipNum - arr[len].ship - x->ship; // 总容纳战舰数减少的数量等于分段后减少的战舰数量 len++; } int main() { cin >> n >> k >> a >> m; init(); // 初始化 for(int i = 1;i <= m; ++i){ cin >> miss; updataNode(miss); // 更新段 if(sumShip < k){ cout << i << endl; return 0; } } cout << -1 << endl; return 0; } //written by zhangjiuding.
代码中涉及到的replace是头文件algorithm中的，
replace（a+3，a+10，p，q）；
表示的是将a[i]（i = [3,9]）中的p全部换成q。