CF-567D One-Dimensional Battle Ships 题解

题目大意

有一个$1\times n$的矩形，上面有k条船，每条船的长度为a，两条船之间不能接触（至少相隔1格）。

给定你m个点，告诉你这些点没有船，问第几次能发现在说谎。

解题思路

这个题目我还真没想到可以这么写。

准确说没啥思路。

先求出最多能放的船的数量。

这个计算一段区间能放船的数量的方法有点神奇，$ans = \frac{(len + 1)}{(a+1)}$。

每条船需要占用$a+1$的空间，但是最后一条船不需要，所以相当于可以补个1.

之后枚举每个点，计算加上这个点之后，减少了多少船，如果船的数量少于k了，就不行。

对于这个点，减少的船的数量就是updown（总的）-middown（右边）-up~mid（左边）。

up和down分别为这个最近的前一个点和后一个点。

为了保证点为有序，需要使用set（其实优先队列也可以，但是不好维护）。

对于set需要用set.upper_bound()来查找，不能使用stl里面的。

这个让我又发现了一个bug，因为stl的upper_bound对set用的时候超时了。

后来查了半天，发现有大佬提出来了，这边贴一下。

set::upper_bound将使用集合的功能有效地搜索值（与容器大小成对数关系）。

对于std::upper_bound，使用非LegacyRandomAccessIterators，比如std::sets迭代器（即LegacyBidirectionalIterators），迭代器增量的数量是线性的。

所以以后需要注意。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define endl '\n'
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

const int N = 2e5 + 5;
int pos[N];
set<int> s;

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

ll qpow(ll a, ll b, ll mod) {
	ll ans = 1;
	while (b) {
		if (b & 1)	ans = (ans * a) % mod;
		a = (a * a) % mod, b >>= 1;
	}
	return ans % mod;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen("D:\\测试用\\in.txt", "r", stdin);
	//freopen("D:\\测试用\\out.txt", "w+", stdout);
	int n, k, a, m; cin >> n >> k >> a >> m;
	rep(i, 1, m) cin >> pos[i];
	s.insert(0), s.insert(n + 1);
	int cnt = (n + 1) / (a + 1), ans = -1;
	auto up = s.begin(), down = s.end();
	rep(i, 1, m) {
		int mid = pos[i];
		up = down = upper_bound(s.begin(), s.end(), mid);
		down--;
		cnt -= (*up - *down) / (a + 1) - (*up - mid) / (a + 1) - (mid - *down) / (a + 1);
		s.insert(mid);
		if (cnt < k) {
			ans = i; break;
		}
	}
	cout << ans << endl;
	return 0;
}