背景

参考了官方题解。

题意

有一条 $1\times n$ 的方格，要放 $t$ 条长度为 $k$ 的船，两条船至少间隔一格。

给定一些攻击，如果打到了一定有船的格子，那么结束程序，否则说明这里没有船。求每个时刻一定有船的格子个数。

保证数据合法。

分析

先看最开始的情况：我们知道这条格子最多装下 $\lfloor\frac{len+1}{k+1}\rfloor$ 条船。如果 $t<\lfloor\frac{len+1}{k+1}\rfloor$，那么每一个格子都不能保证有船（有至少一整条船的空位，可以腾出来给每条船）；否则有 $x=(len+1)\bmod(k+1)$ 个空位，船可以左右滑动，但每条船都能确定 $k-x$ 个格子（其实可能是 $0$ 个），所以总共有 $t \times (k-x)$ 个格子一定有船。

最开始的问题是算区间 $[1,n]$ 的能确定格子的个数。

每次攻击，我们找到攻击目标所在的区间，把它从攻击的位置裂成两段，更新答案。这个过程可以用 set 维护。

实现

#include<bits/stdc++.h>
using namespace std;
int n,t,k,ship,cnt;
struct Itv
{
	int l,r;
	int len()
	{
		return r - l + 1;
	}
	int s()
	{
		return (len() + 1) / (k + 1);
	}
	int c()
	{
		return max(0,s() * (k - (len() + 1) % (k + 1)));
	}
	bool operator < (const Itv &a) const
	{
		return l < a.l;
	}
};
set<Itv> s;
void add(Itv x)
{
	if(x.l <= x.r) s.insert(x),ship += x.s(),cnt += x.c();
} 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>t>>k;
	add({1,n});
	if(ship == t) cout<<cnt<<endl;
	else cout<<0<<endl;
	while(1)
	{
		int tar;
		cin>>tar;
		Itv x = *(-- s.upper_bound({tar,tar}));
		s.erase(x),ship -= x.s(),cnt -= x.c();
		add({x.l,tar - 1}),add({tar + 1,x.r});
		if(ship < t)
		{
			cout<<1<<endl;
			return 0;
		}
		cout<<"0 ";
		if(ship == t) cout<<cnt<<endl;
		else cout<<0<<endl;
	}
	return 0;
}