GYM-102893J Straight 模拟 思维
题意
值域([1,n])内有(m)个已经放置好的点，尚有(s)个隐藏点可以随意放置。
问有多少种方案，使得存在连续点(i,i+1...i + m +1)
(m)个已经放置好的点有可能重叠
[1 leq n leq 1e9\
1leq 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;
}