【题解】疫情食堂
题意
给你三个整数,表示一开始有
个位置,其中
个位置是做人的,并给出这
个人的位置。任意两个人之间应该空出
个位置落座。问还可以让多少个人坐呢。
题解
模拟即可,我们首先记录两个被占座位置之间有多少个空位呢,由于两个人的座位之间要空出个位置,所以假设若当前有
个空位在已经坐人的位置之前要空出
个位置,所以还剩下
个位置可以选择。那么每次选择的是一个坐人的以及
个空位置,所以就是
个是可以插入的。这样从
遍历到
即可。
复杂度
时间复杂度
代码
#include<bits/stdc++.h> using namespace std; const int N=2e5+5; int vis[N]; int main() { int t; scanf("%d",&t); while(t--) { memset(vis,0,sizeof(vis)); int n,m,k; scanf("%d%d%d",&n,&m,&k); for(int i=0; i<m; i++) { int x; scanf("%d",&x); vis[x-1]=1; } int d=k; int ans=0; for(int i=0; i<n; i++) { if(vis[i]==0) d++; else { d-=k; ans+=d/(k+1); d=0; } } printf("%d\n",ans+d/(k+1)); } return 0; }