-
开始给你\(N\)个元素的数组(下标从$ 1 $开始),数组里的数是\(1,2,3,…,N\),然后执行\(D\)次删除操作。每次删除操作给一个区间\([lo, hi]\),要求删除下标位置从\(lo\)到\(hi\)的数,数组里的数据个数会减少\(hi-lo+1\)个。
-
例如,N=8,第1次删除操作区间是\([3,4]\),结果为“\(1,2,5,6,7,8\)”; 第2次删除操作区间是\([4,5]\),结果为“\(1,2,5,8\)”。
-
最后,输出第\(M\)位的数字是什么。如果剩余的数不够\(M\)个,输出\(-1\)。
- 这道题是典型的倒推思想,我们盯着最后结果的第\(M\)位,从后往前,研究它每经过一次处理后所在位置就可以得到了。如果删除的位置在定位的前面,则定位向后退,否则无影响。
#include<bits/stdc++.h>
using namespace std;
vector <int> a;
int T,n,m,d,l,be,en,zz,ans,gk;
string st[55];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&gk,&d);
m=gk;ans=0;
for(int i=1; i<=d; i++)cin>>st[i];
for(int i=d; i>=1; i--)
{
be=0;en=0;zz=0;
l=st[i].size();
while(st[i][zz]!='-'){be=be*10+st[i][zz]-'0';zz++;}
zz++;
for(int j=zz; j<l; j++) en=en*10+st[i][j]-'0';
ans=ans+(en-be+1);
if(be<=m) m=m+(en-be+1);
}
if(gk>(n-ans))printf("-1\n");
else printf("%d\n",m);
}
return 0;
}