题解：CF1041D Glider

前置知识

你需要了解基础语法、前缀和、二分，并掌握一定的推导能力；本篇题解补充了其他题解模糊不清的要点。

思路讲解

题面比较乱，这里简要概括：某飞行员要跳伞，允许在任何点跳下飞机，从高度

h

开始每秒下降一点、前进一点；同时给出

n

个不相交区间，经过区间时飞行员不会下降，只会前进；我们要求出最远飞行距离。

显然，飞行员从某一区间的左端点开始跳是最优的，那我们不妨枚举每一个区间左端点作为起点的情况，求解后更新答案。

考虑前缀和优化，我们预处理出到达第

i

个区间需要下降的距离，即非区间内的距离；每次求解时，二分查找最后一个能到达的完整区间；计算答案时，先累加起始区间左端点到结束区间右端点的距离，再加上可能的剩余飞行距离（可能飞出找到的区间，但未能到达下一个区间），最后更新最大值。

代码展示

注意计算答案的过程，理清思路再慢慢写，以下代码仅供参考：

CPP

#include<bits/stdc++.h>

using namespace std;

#define inf 0x3f3f3f3f
#define ll long long
#define ld long double
#define endl '\n'

#define int long long

// 快速读入，快速输出，可选 
inline int read() {int x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9') { if (ch == '-') w = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') {  x = x * 10 + (ch - '0');ch = getchar();}return x * w;}
void write(int x) {static int sta[35];int top = 0;do {sta[top++] = x % 10, x /= 10;} while (x);while (top) putchar(sta[--top] + 48); }
 
int n,h,maxn; // 定义变量 
int l[1000007]; // 左端点 
int r[1000007]; // 右端点 
int s[1000007]; // 前缀和预处理数组 

signed main(){
	n=read(),h=read(); // 读入区间数量和高度 
	for(int i=1;i<=n;i++){
		l[i]=read(),r[i]=read(); // 读入左右端点 
		s[i] = s[i-1]+(l[i]-r[i-1]); // 到达第 i 个区间需要下降的距离，也可以说是非区间内的距离
		// 上一区间的值，加上上一区间到这一区间的下降距离
	}
	
	for(int i=1;i<=n;i++){ // 枚举每个区间左端点作为起点的情况 
		int j=lower_bound(s+1,s+1+n,h+s[i])-s-1; // 计算最后一个可以到达的完整区间 
		int ans=r[j]-l[i]+(h-s[j]+s[i]); // 当前区间到最后区间的距离，加可能的剩余距离，就是答案 
		maxn = max(maxn,ans); // 更新最大值 
	} 
	cout<<maxn; // 输出最大值 
	
	return 0; // 这题做完了！ 
}

题解：CF1041D Glider

文章操作

前置知识

思路讲解

代码展示

相关推荐

评论

题解：CF1041D Glider