浅奥算法编程系列1:格蕾丝的逃离

大多数编程问题，其实都是数学建模+算法实现的过程。浅奥训练的是逻辑思维和数学建模能力，而编程则是把这些思路落地成可执行代码的工具，两者结合能形成 “思维 + 实践” 的双向促进。通过浅奥题的推导，我们能提炼出清晰的算法逻辑，反过来，用代码验证这些逻辑的过程，又会倒逼我们把浅奥里的抽象关系想得更严谨。

今天这道《格蕾丝的逃离》，就是一次绝佳的练手机会：既用浅奥的追及模型理清了问题本质，又能用编程高效完成方案计数，让你在解题中同时收获思维和代码能力的提升。

核心解题思路

这道题的核心是先通过浅奥数学建模简化问题，再用编程技巧高效求解，分为两步走，层层递进：

1.  浅奥数学推导：提炼核心判断条件

首先把实际问题转化为数学不等式，这是解题的关键，也是浅奥思维的体现。

相信有部分同学已经观察到这个问题属于小学浅奥中的同向行驶追击问题。公主被抓到的前提是，革命军到达城池的时间早于公主到达城池的时间。

设：革命军的马速为 v1，公主的马速为 v2

• 公主到城池的距离为 L，革命军与公主的初始距离为 D，革命军到城池的距离D+L

推导过程：

1. 公主跑到城池需要的时间：
2.       t_公主 = L / v2
3. 革命军跑到城池需要的时间：
4.           t_革命军 = (L+D) / v1
   革命军要在公主进城前追上她：
             t_公主 > t_革命军

2.  暴力枚举思路

• 暴力解法：枚举所有 (v1, v2) 组合，时间复杂度 O(N²)，当 N 很大（比如上万）时，程序会超时。

#include<bits/stdc++.h>using namespace std;int v[200002];intmain(){	int D,L;	int n;	cin >> D >> L;	cin >> n;	for(int i=1; i<=n; i++) {		cin >> v[i];	} 	// i - 革命军， j - 公主	//（D+L）/v[i] < L/v[j]	// (D+L)*v[j] < v[i]*L	int cnt = 0; 	for(int i=1; i<=n; i++) {		for(int j=1; j<=n; j++) {			if((D+L)*v[j] < v[i]*L) {				cnt++;			}		}	}	cout << cnt;	return 0;} 

• 高效解法：先对速度数组排序，再用二分查找快速统计符合条件的 v2 数量，时间复杂度优化到 O(N log N)，效率大幅提升。

具体步骤：

1. 遍历每个革命军的速度 v1，计算对应的临界值 target = (v1 * L) / (L+D)（这里用浮点数接收，方便后续二分查找）。
2. 对于排序后的数组，用二分查找找到第一个大于等于 target 的元素下标，这个下标就是满足 v2 < target（即 v1 * L > v2 * D）的 v2 数量。
3. 累加所有 v1 对应的符合条件数量，最终得到总方案数。

#include<bits/stdc++.h>using namespace std;int v[200002];// 临界点 (L+D)/v1 = L/v2// v2 = L*v1/(L+D) - v2代表公主和土匪同时跑到城池，没有抓住// 所以找到小于v2的最大位置。从1到该位置的速度都是符合要求的。 longlongfindhorse(int L, int D, int v1, int n){	double v2 = 1.0*L*v1/(L+D);	int l = 1, r = n;	long long ans = 0;	while(l<r) {		int mid = (l + r)/2;		if(v[mid]<v2) {			ans = mid;			l = mid+1;		} else {			r = mid;		}	} //	cout << "v1=" << v1 << " v2=" << v2 << " ans=" << ans << endl;	return ans;}intmain(){	int D,L;	int n;	cin >> D >> L;	cin >> n;	for(int i=1; i<=n; i++) {		cin >> v[i];	} 	sort(v+1, v+n+1);	long long cnt = 0; 	for(int i=1; i<=n; i++) {		// v1 - 革命军的马速度 		int v1 = v[i];		// 满足单调性，可以使用二分查找		cnt += findhorse(L, D, v1, n);	}	cout << cnt;	return 0;} 

总结

1. 对于此类浅奥题，核心是识别数学模型。并构造关键的数学公式。
2. 具体到本题，解题核心是将浅奥追及问题转化为 L*v1 > (L+D)*v2 的数学不等式，避开复杂的时间计算，简化逻辑。
3. 在代码实现上，可以先使用暴力枚举得到部分分数。   
4. 更优化的解法是，先排序再用二分查找，将时间复杂度优化到 O(N log N)，同时用 long long 防止大数溢出。

关注信息学小助手，获取经济实用的C++入门方案。有想学习C++的，可以在公众号留言，或者联系信息学小助手。

作者简介：华中科技大学本硕，前华为工程师，现高校大数据专业算法课老师。

获得PTA满分认证，可以推荐跨级靠GESP

https://pta.ccf.org.cn/cms/news/100000/0000000114/2025/11/1/514e24a9de984b888ed03803a2fa4434.shtml