codeforces 567D.One-Dimensional Battle Ships 解题报告

题目链接：http://codeforces.com/problemset/problem/567/D

题目意思：给出 1 * n 的 field，编号从左至右依次为 1,2，...，n。问射 m 枪之后（第 i 次射中编号 xi，则 xi 这一点是不能放置船只的！），能不能将 k 只 1 * a 的小船放到这些没有经过被射中编号的 field 中 。由于Alice 每次 shoot 的时候都会说 miss 的，即没有打中，你需要判断第几次shoot 使得整个field 不能放置 k 只 小船，如果都能放，最终输出 - 1.

　　首先，外国人的题解真是好严谨，又好体~~~

　　有几点需要解释下。事实上这几点也困惑了我好久 0.0

　　（1）一开始整个区间 (n+1)/(a+1) 可能好多人还是不太明白。那么列条方程帮助理解吧。假设在[1, n] 中最多可以放置 x 只船，可以列出 x * a + (x - 1) = n，于是经若干合并同类项，就可以得到 x =  (n+1)/(a+1)。或者可以按题解者那样理解，由于最大放船数肯定是从最边边开始放的啦，然后间隔一个shoot之后随之放入另一只船。。。很容易知道，每只船占的空间至少为a+1（最尾那只可能不止又或者是a（可喜可贺啊）），那么我们可以虚拟多一个编号为 n+1 的 field。所以整个长度就为 （n+1）/ (a+1)了，很神奇哇~

　　（2）(r-l+2)/(a+1) 是啥来的？！如果理解了第一点就很容易明白了。我们shoot完之后，这个 shoot 将空间一分为二了，选定的空间我们用集合set 的 upper_bound来找，返回的是 r ，前一个就是  l 。r-l+1很容易理解（不理解可以私聊我），再+1 就是虚拟的那个field。第（1）点已经说了，紧挨着边放置是最优解的条件！最后记得把shoot这个编号放入下一轮备选空间上。

　　（3）空间中为什么要减完再加。因为有个shoot将空间一分为二嘛~~这个时候可以放置的船已经不是原来的[l, r] 这么多了。而是被分开的左区间[l, x-1] 和 [x+1, r] 之和这么多。

　　

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <algorithm>

 #include <set>

 using namespace std;

 set<int> s;

 int main()

 {

     #ifndef ONLINE_JUDGE

         freopen("in.txt", "r", stdin);

     #endif // ONLINE_JUDGE

     int m, n, a, k, x;

     while (scanf("%d%d%d", &n, &k, &a) != EOF) {

         scanf("%d", &m);

         s.clear();

         s.insert(), s.insert(n+);   // 实现虚拟长度的小技巧

         int sum = (n+) / (a+);

         int ans = -, f = ;

         for (int i = ; i <= m; i++) {

             scanf("%d", &x);

             set<int>::iterator it = s.upper_bound(x);

             int r = *it;

             int l = *(--it);

             sum = sum - (r-l)/(a+) +(x-l)/(a+) + (r-x)/(a+);

             if (sum < k && !f) {

                 ans = i;

                 f = ;

             }

             s.insert(x);

         }

         printf("%d\n", ans);

     }

     return ;

 }