GYM-102893J Straight 模拟 思维

题意

值域\([1,n]\)内有\(m\)个已经放置好的点，尚有\(s\)个隐藏点可以随意放置。

问有多少种方案，使得存在连续点\(i,i+1...i + m +1\)

\(m\)个已经放置好的点有可能重叠

\[1 \leq n \leq 1e9\\ 1\leq s \leq 1e5 \]

分析

我们枚举已经放置好的点来计算答案。

先对原数组排序并去重，记剩下的点为个数为\(siz\)

当以\(v[i]\)为已知点的起点时，对于\(0 < i\)的已知点都不能加入连续段，因此连续段的起点最小值应该为\(v[i - 1]+1\)，\(i = 1\)时，则为\(1\)，最大值应该不超过\(v[i]\)。

需要\(m\)个点，那么至少还需要\(m - s - 1\)个已知点，那么连续段终点应该至少为\(v[i + m - s - 1]\) ，终点 = 起点 + m - 1，那么起点应该至少为\(v[i + m - s- 1] - m - 1\)。

同时，考虑到\(n\)的限制，终点应该不超过\(n\),因此起点也应该不超过\(n - m - 1\)。

综上，起点最小值记作\(low\),起点最大值记作\(up\)。

\[low = max(v[i - 1] + 1,1,v[i + m - s - 1] - m - 1)\\ up = min(v[i],n - m - 1) \]

最后，对这些线段去交集，统计即可。

代码

int main(){
	int n = rd();
	int m = rd();
	int s = rd();
	vector<int> tmp(m);
	for(int i = 0;i < m;i++)
		tmp[i] = rd();
	sort(tmp.begin(),tmp.end());
	vector<int> v;
	for(int i = 0;i < m;i++)
		if(!v.empty() && v.back() == tmp[i]) continue;
		else v.push_back(tmp[i]);
	int siz = (int)v.size();
	
	ll ans = 0;
	vector<pii> p;
	for(int i = 0;i < siz;i++){
		if(i + m - s - 1 >= siz || i + m - s - 1 < 0) continue;
		int low = v[i + m - s - 1] - m + 1;
		int up = min(v[i],n - m + 1);
		low = max(1,low);
		if(up < 0 || low > up) continue;
		p.push_back(make_pair(low,up));
	}	
	if(p.empty()) {
		puts("0");
		return 0;
	}
	vector<pii> res;
	sort(p.begin(),p.end());
	int l = p[0].fi,r = p[0].se;
	for(int i = 1;i < p.size();i++){
		if(p[i].fi <= r) r = max(r,p[i].se);
		else{
			res.push_back(make_pair(l,r));
			l = p[i].fi;
			r = p[i].se;
		} 
		if(i == p.size() - 1) res.push_back(make_pair(l,r));
	}
	for(auto it:res){
		ans += it.se - it.fi + 1;
	}
	cout << ans;
}