1. 小信抗辐射(2)
题目ID：20431必做题文件操作100分
最新提交：
Runtime Error
0 分
历史最高：
Runtime Error
0 分
时间限制: 1000ms
空间限制: 262144kB
输入文件名: B.in
输出文件名: B.out
题目描述
小信正在玩一个游戏，在某个有辐射的副本中，该副本有 nn 个关卡，每一关都有一个辐射值aiai，所以小信需要选一件抗辐射值为 xx 的衣服，只要衣服的抗辐射值 xx 大于等于当前关卡的辐射值 aiai，小信就有可能通过该关。
此外，小信在通过第 ii 关后，下一关只能选择在区间 [i+l,i+r][i+l,i+r] 内的关卡进入，其中 l≤rl≤r。
小信初始在第 1 关，当小信可以跳过第 nn 关时即为通关，也可以理解为通过第 ii 关并且 i+r>ni+r>n 时，视为通关。
因为抗辐射值越高的衣服越贵，请帮助小信找出满足条件的最小抗辐射值。
输入格式
第一行包含一个整数 TT ，表示测试用例的数量。
每个测试用例的第一行包含三个整数 n,l,rn,l,r ，分别表示关卡数、最小步长和最大步长。
第二行包含 nn 个整数 a1,a2,…,ana1,a2,…,an ，表示每一关的辐射值。输出格式
对于每个测试用例，输出一个整数，表示满足条件的最小抗辐射值。
样例
Input 1
2 5 1 2 2 3 2 5 1 3 2 3 10 10 10
Output 1
2 10
数据范围
- 1≤T≤201≤T≤20
- 1≤n≤2000001≤n≤200000
- 1≤l≤r<101≤l≤r<10
- 1≤ai≤1091≤ai≤109
- 30%30% 的数据满足：1≤n≤101≤n≤10
- 其余 70%70% 的数据满足：1≤n≤2000001≤n≤200000
代码:
#include<bits/stdc++.h>
using namespace std;
int t;
int n,l,r;
int a[200005];
bool dfs(int x,int pass,int awa){//当前关卡，通关的关卡（到达该关卡及之后的任何关卡就算通过)防御值
if(x>=pass){
return 1;
}
bool flg=0;
for(int i=min(x+l,n);i<=min(i+r,n);i++){
if(a[i]>awa){
continue;
}
if(dfs(i,pass,awa)){
flg=1;
break;
}
}
return flg;
}
int main(){
//freopen("B.in","r",stdin);
//freopen("B.out","w",stdout);
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&l,&r);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
int l=a[1]-1,r=1e9;
while(l<=r){
int mid=l+(r-l)/2;
if(dfs(1,n-r+1,mid)){
r=mid-1;
}
else{
l=mid+1;
}
}
cout<<l+1<<endl;
}
return 0;
}
/*
*/
提交的时候去了freopen的注释