#include <bitsdc++.h> #define x first #define y second using namespace std; typedef long long LL; typedef pair<LL, LL> PII; const LL N = 55,INF=0x3f3f3f3f3f3f3f3f,mod=1e9+9; typedef long long LL; LL n,m,f[N],a[N],bl[N],br[N],b[N]; bool check(LL x) { memset(bl,0,sizeof bl); memset(br,0,sizeof br); bool flag=true; for(int i=1;i<=n;i++) { bl[i]=max((LL)0,a[i]-x); br[i]=a[i]+x; } for(int i=1;i<=n;i++) b[i]=max(bl[i],b[i-1]+1); for(int i=1;i<=n;i++) if(abs(a[i]-b[i])>x) return false; return true; } int main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; LL l=0,r=1e9; while(l<r) { LL mid=l+r>>1; //cout<<mid<<endl; if(check(mid)) r=mid; else l=mid+1; } cout<<l; return 0; }
时间: 2024-04-28 12:27:04 浏览: 10
这是一段 C++ 代码,实现了一个二分答案的算法来解决一个问题。具体来说,它解决的是一个跳跃游戏问题,给定一个长度为 $n$ 的数组 $a$,每个元素表示在该位置上最多可以跳 $a_i$ 步,问是否存在一种跳跃方式,能够从位置 $1$ 跳跃到位置 $n$。如果存在,则输出最小的跳跃步数,否则输出 $-1$。
代码中的 check 函数实现了检查当前二分答案 $x$ 是否可行的功能。具体来说,它首先根据 $a$ 数组和 $x$ 计算出一个区间 $[bl_i,br_i]$,表示在位置 $i$ 上可以跳跃到的最远距离。然后,它再用一个辅助数组 $b$ 计算出从位置 $1$ 到位置 $i$ 上最远可以跳跃到哪里,即 $b_i=\max\{bl_i,b_{i-1}+1\}$。最后,它检查是否有某个位置 $i$,满足 $|a_i-b_i|>x$,如果有,则说明当前答案 $x$ 不可行,返回 false。如果所有位置都满足该条件,则说明当前答案可行,返回 true。
主函数中使用二分答案来解决问题。具体来说,它首先初始化二分区间 $[l,r]$,其中 $l=0,r=10^9$。然后,每次取 $mid=l+r>>1$,调用 check 函数检查当前二分答案 $mid$ 是否可行。如果可行,则将二分区间缩小到 $[l,mid]$,否则将二分区间缩小到 $[mid+1,r]$。最终,当 $l=r$ 时,输出 $l$ 即为答案。
相关问题
#include+<stdio.h> #include+<stdlib.h> #include+<string.h> typedef+int+DataType; #define+QUEUESIZE
这段代码是C语言中的头文件引用部分,含了三个头文件:stdio.h、stdlib.h和string.h。
- stdio.h是C语言标准库中的头文件,提供了输入输出函数的声明和定义,例如printf和scanf等。
- stdlib.h也是C语言标准库中的头文件,提供了一些常用的函数和类型定义,例如内存分配函数malloc和free等。
- string.h是C语言标准库中的头文件,提供了字符串处理函数的声明和定义,例如strcpy和strlen等。
typedef+int+DataType;这行代码定义了一个新的数据类型DataType,它是int类型的别名。
#define+QUEUESIZE这行代码使用宏定义方式定义了一个常量QUEUESIZE,它表示队列的大小。
根据数据结构知识给下面代码添加注释:#include+<stdio.h> #include+<stdlib.h> #include<string.h> #define+MAX_NAME+5 #def
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NAME 5
#define MAX_DETAIL 10
// 定义结构体
typedef struct {
char name[MAX_NAME];
char detail[MAX_DETAIL];
} FamilyMember;
int main() {
// 创建一个FamilyMember类型的数组
FamilyMember members[3];
// 给数组中的每个成员赋值
strcpy(members[0].name, "John");
strcpy(members[0].detail, "Father");
strcpy(members[1].name, "Mary");
strcpy(members[1].detail, "Mother");
strcpy(members[2].name, "Tom");
strcpy(members[2].detail, "Son");
// 打印数组中的每个成员的姓名和注释
for (int i = 0; i < 3; i++) {
printf("Name: %s\n", members[i].name);
printf("Detail: %s\n", members[i].detail);
printf("\n");
}
return 0;
}
```
这段代码定义了一个结构体`FamilyMember`,包含了姓名和注释两个成员变量。然后创建了一个`FamilyMember`类型的数组`members`,并给数组中的每个成员赋值。最后,通过循环打印数组中每个成员的姓名和注释。