Note: This article is available in Chinese only. 本文暂无英文版本。
View original
比赛的时候没搞出来，really sad. 其实这题很容易啊．．．． 首先，对于lie 的判断应该基于能放的船的个数． 能放的船的个数是随着射的点数的增加而减少的． 射完每个点后更新能放的船的个数，如果这个时候已经无法放下k条船了，说明lie了． 如果所有都射完也没发生，那么就-1.
由于船与串不能相邻，除了最后一条船，每条船实际占的size 应该为a+1 那么很容易知道对于长度为l的区间，能放的船的个数为（l+1）/(a+1) 这是初始能放的船的个数，为最大值． 当射了点b之后，破坏的是b所在的一段最大的没有被射过点的区间的连续性． 做法是找到距离b点最近的左端和右端的被射过的点． 可以用set 搞，找的时候upper_bound 记得初始化的时候把 0点和 n+1 点当成射过的．
代码实现
1/*************************************************************************
2 > File Name: code/cf/#314/D.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年08月16日 星期日 00时27分54秒
6 ************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#define y0 abc111qqz
21#define y1 hust111qqz
22#define yn hez111qqz
23#define j1 cute111qqz
24#define tm crazy111qqz
25#define lr dying111qqz
26using namespace std;
27#define REP(i, n) for (int i=0;i<int(n);++i)
28typedef long long LL;
29typedef unsigned long long ULL;
30const int inf = 0x7fffffff;
31set<int> se;
32int n,k,a,m,b;
33set<int>::iterator it;
34int cal (int x,int y) //cal 函数计算出当射了b之后，因此减少的能放船的个数．
35{
36 int res;
37 res = (y-x)/(a+1)-(y-b)/(a+1)-(b-x)/(a+1);//由于射了b点，相当于之前连续的区间(x,y)被分成了（x,b）和（b,y)
38 //(x,y)区间能放的船的数量由之前变成了被分成的两个小区间能放的船的数量的和．
39 return res;
40}
41int main()
42{
43 scanf("%d %d %d",&n,&k,&a);
44 scanf("%d",&m);
45 se.clear();
46 int sum=(n+1)/(a+1); //sum表示的是当前能放的船的个数
47 //容易知道，对于长度为l的点，最多能放的船的数量为（l+1）/(a+1);
48 se.insert(0);
49 se.insert(n+1);//由于要找要被射的点两遍最近的被射的点，我们不妨认为0点和n+1点也是被射的，这样处理断点容易些．
50 int ans = -1;
51 bool flag = false;
52 for (int i=1;i<=m;i++)
53 {
54 scanf("%d",&b);
55 if (flag) continue;
56 it=se.upper_bound(b);
57 int y=*it;
58 int x=*(--it); //y和x分别是离b点最近且已经被射的点
59 sum = sum - cal(x,y);
60 if (sum<k)
61 {
62 ans = i;
63 flag = true;
64 }
65 se.insert(b);
66 }
67 cout<<ans<<endl;
68 return 0;
69}