第二章 基本算法
2.1 算法复杂度
2.1.1算法的概念
算法是对特定问题求解的一种描述，是指令的有限序列。算法有以下5个特征：
- 输入：一个算法可以有一个或零个输入；
- 输出：一个算法有一个或多个输出，算法可以没有输入，但一定要有输出；
- 确定性：算法中每条指令必须有确切的含义
- 有穷性：一个算法必须在执行有穷布之后结束，每一步多必须在有穷时间内完成；
- 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
2.1.2复杂度和大O记号
衡量算法性能主要考虑时间复杂度，一般不考虑空间复杂度。衡量算法运行时间最常见的一种方法是大O记号。它表示一个算法或函数的渐进上界。在大O分析中，规模n前面的常数系数会被省略。一个代码或算法的时间复杂度有以下情况：
-
O(1)
计算时间是一个常数，与问题规模无关。例如在矩阵
A[M][N]查找第i行第j列的元素。此外，贪心法的时间复杂度往往也是O(1)。 -
O(\log_2 n)
计算时间是一个对数，即每步计算后，问题的规模缩小一半，例如二分法、倍增法、分治法的复杂度都是O(\log_2n)。它与O(1)没有太大差别，计算量都很小。
-
O(n)
计算情况随规模n线性增长。很多情况下，这是算法可能达到的最优复杂度。
-
O(n\log_2n)
O(n\log_2n)常常是算法能够达到的最优复杂度。例如分治法对n个数每个都操作一次，总复杂度为O(n\log_2n)。利用分治法思想的快速排序算法和归并排序算法，复杂度就是O(n\log_2n)。
-
O(n^2)
一个二重算法的复杂度为O(n^2)，如冒泡排序。类似的还有O(n^3)，O(n^4)，比如说矩阵乘法和Floyd算法，都是三个循环。
-
O(2^n)
一般对应集合问题，例如求一个集合中的所有子集。
-
O(n!)
求全排列问题。
我们可以将以上的复杂度分为多项式复杂度（O(1),O(\log_2n),O(n),O(n\log_2n),O(n^k)）和指数复杂度（O(2^n),O(n!)）。多项式复杂度对应的算法称为高效算法，而指数复杂度对应的算法称为低效算法，低效算法的计算量增长速度远远超过了硬件的增长。
对于算法竞赛来说，如果用千万次估算复杂度，则可以反推出能解决问题的问题规模：
| 问题规模n&可用算法的时间复杂度 | O(\log_2n) | O(n) | O(n\log_2n) | O(n^2) | O(2^n) | 0(n!) |
|---|---|---|---|---|---|---|
| n\le11 | ✔ | ✔ | ✔ | ✔ | ✔ | ✔ |
| n≤25 | ✔ | ✔ | ✔ | ✔ | ✔ | ❌ |
| n \le 5000 | ✔ | ✔ | ✔ | ✔ | ❌ | ❌ |
| n≤10^6 | ✔ | ✔ | ✔ | ❌ | ❌ | ❌ |
| n\le10^7 | ✔ | ✔ | ❌ | ❌ | ❌ | ❌ |
| n>10^8 | ✔ | ❌ | ❌ | ❌ | ❌ | ❌ |
在学习算法和解算法题时，请自觉分析时间复杂度和空间复杂度。
除了用大O记号分析，还有一种平摊分析方法，会在未来介
2.2 尺取法（双指针）
2.2.1 尺取法的概念
尺取法的应用背景：
- 给定一个序列，有时需要它是有序的，先排序；
- 问题和序列的区间有关，且需要操作两个变量，可以用两个下标（指针）i和区间。
尺取法就是将二重循环变为一个循环，在这个循环中同时处理i和j。这样就从O(n^2)变为O(n)。伪代码如下：
int i = 0, j = n - 1;
while (i < j) {
...
i++;
j--;
}
for (int i = 0, j = n - 1; i < j; i++, j--) {
...
}
- 两种扫描方式：
- 反向扫描，i和j的方向相反，在中间相会。称为左右指针。
- 同向扫描，i和j的方向相同，j跑在i前面。称为快慢指针。
2.2.2 反向扫描
下面介绍几个经典的反向扫描的编码方法：
- 找指定和的整数对：
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
尺取法的代码如下：
# 尺取法，寻找指定和的整数对
class Solution:
def pairSums(self, nums, target: int):
nums.sort()
res = []
i, j = 0, len(nums) - 1
while i < j:
if nums[i] + nums[j] == target:
res.append([nums[i], nums[j]])
i += 1
j -= 1
elif nums[i] + nums[j] < target: # 比目标值小，小的数往大走
i += 1
else: # 比目标值大，大的数往小走
j -= 1
return res
if __name__ == "__main__":
s = Solution()
nums = [21, 4, 5, 6, 13, 65, 32, 9, 23]
target = 28
print(s.pairSums(nums, target))
注意：本题还可以用同向扫描的方法来做。
- 判断回文串
// 判断回文串，使用尺取法
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
while(n--) {
string s;
cin >> s;
bool ans = true;
int i = 0, j = s.size() - 1;
while(i < j) {
// 如果字符不相等，则ans为false
if(s[i]!= s[j]) {
ans = false;
break;
}
i++;
j--;
}
if(ans) cout << "yes" << endl;
else cout << "no" << endl;
}
return 0;
}
2.2.3 同向扫描
- 寻找区间和
寻找区间和
问题描述：给定一个长度为n的数组a[]和一个数s,在这个数组中找一个区间，使这个区间的数组元素之和等于s。输出区间的起点和终点位置。
说明：输入样例的第1行是n=15,第2行是数组a[],第3行是区间和s=6。输出样例共有4种情况。输入样例
15 6 1 2 3 4 6 4 2 8 9 10 11 12 13 14 6输出样例
0 0 1 3 5 5 6 7
# 尺取法，寻找区间和
n = int(input())
a = list(map(int, input().split()))
s = int(input())
i, j = 0, 0
ans = a[0]
while j < n:
if ans >= s:
if ans == s:
print(i, j)
ans -= a[i]
i += 1
if i>j:
if i == n:
break
ans = a[i]
j += 1
else:
j += 1
if j == n:
break
ans += a[j]
这是一个典型的滑动窗口的例子，滑动窗口的例子还有：
-
给定一个序列以及整数M，在序列中找M个连续递增的元素，使他们的区间和最大；
-
给定一个序列以及一个整数K，求一个最短的连续子序列，其中包含至少K个不同的元素；
-
数组去重
尺取法的方法如下：
- 将数组排序，排序后重复的整数就会挤在一起。
- 定义双指针i,j。初始值都指向a[0]。i和j都从头到尾扫描数组a[]。i指针走的快，逐个遍历整个数组；j指针走的慢，它始终指向当前不重复部分的最后一个数。
- 扫描数组。快指针执行i++，如果此时a[i]不等于慢指针指向的a[j]，就执行j++。并且把a[i]复制到慢指针j的当前位置a[j]。
- i扫描结束后，a[0]~a[j]就是不重复数组。
# 尺取法，数组去重
def removeDuplicates(nums):
i, j = 1, 0
nums.sort()
while i < len(nums):
if nums[i] == nums[j]:
i += 1
if i == len(nums):
break
if nums[i] != nums[j]:
j += 1
nums[j] = nums[i]
return nums[:j+1]
if __name__ == "__main__":
nums = [9,7,6,4,7,43,23,5,76,4,6,78,45,3,4,65,7,5,3,2,3,4,5,6,7,8]
print(removeDuplicates(nums))
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int removeDuplicates(int nums[], int numsSize) {
int j = 0;
for (int i = 1; i < numsSize; ++i) {
if (i == 0 || nums[i] != nums[j]) {
nums[++j] = nums[i];
}
}
return j + 1;
}
int main() {
int nums[] = {9, 7, 6, 4, 7, 43, 23, 5, 76, 4, 6, 78, 45, 3, 4, 65, 7, 5, 3, 2, 3, 4, 5, 6, 7, 8};
int numsSize = sizeof(nums) / sizeof(nums[0]);
sort(nums, nums + numsSize);
int uniqueNumsSize = removeDuplicates(nums, numsSize);
for (int i = 0; i < uniqueNumsSize; ++i) {
std::cout << nums[i] << " ";
}
return 0;
}
- 多指针
找相同数对
问题描述：给出一串数以及一个数字C,要求计算出所有A-B=C的数对的个数(不同位置的数字一样的数对算不同的数对)。
输入：共两行。第1行输入两个整数n和C；第2行输入n个整数，作为要求处理的那串数。
输出：该串数中包含的满足A-B=C的数对的个数。
数据范围：1≤n≤2×10^5；所有输入数据绝对值小于2^{30}。输入样例
6 3 8 4 5 7 7 4输出样例
5
出现重复的数，找数对就不能用双指针，可以用三指针i,j,k。其中j,k表示一个范围，范围内是全都是相同的数，i是快指针。
// 三指针找相同数对
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int a[N];
int main() {
int n, c;
cin >> n >> c;
for (int i = 1; i < n + 1; i++) cin >> a[i];
sort(a + 1, a + n + 1);
long long ans = 0;
for (int i = 1,j = 1, k = 1;i <= n; i++) {
while(j <= n && a[j] - a[i] < c) j++;
while(k <= n && a[k] - a[i] <= c) k++;
if(a[j]-a[i] == c && a[k - 1] - a[i] == c && k-1 >= 1 )
ans += (long long)(k - j);
}
cout << ans << endl;
return 0;
}
# 三指针找相同数对
n, c = map(int, input().split())
a = list(map(int, input().split()))
a = a + [0]
a.sort()
ans = 0
for i in range(1, n + 1):
j = k = i + 1
while j <= n and a[j] - a[i] < c:
j += 1
while k <= n and a[k] - a[i] <= c:
k += 1
try:
if a[j] - a[i] == c and a[k - 1] - a[i] == c and k - 1 >= 1:
ans += (k - j)
except:
pass
print(ans)
此外，尺取法在链表中还有一些应用：
- 判断链表中是否含有环；
- 已知链表中有环，返回这个环的起始位置；
- 寻找链表的中点；
- 寻找链表的倒数第k个元素。
练习题：
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
while (n--)
{
int x, y;
cin >> x >> y;
int a[100010];
int sum = 0;
for (int i = 0; i < x; i++)
{
cin >> a[i];
sum += a[i];
}
int i = 0, j = 0, s = a[0];
int ans = x;
if (sum < y) // 数组总和没目标值大，区间为0
{
cout << 0 << endl;
continue;
}
while (j < x) // 双指针
{
while (s < y && j < x)
{
j++;
if (j < x)
s += a[j];
}
while (s >= y && i < x)
{
if (ans > j - i)
ans = j - i + 1;
s -= a[i];
i++;
}
}
cout << ans << endl;
}
return 0;
}
# 洛谷P1102 A-B 数对
if __name__ == "__main__":
n, m = map(int, input().split())
a = list(map(int, input().split()))
i, j, k = 1, 0, 0 # 三指针，jk在后，表示区间，i在前
a.sort(reverse=True)
ans = 0
while i < n:
while a[j] == a[k]:
k += 1
if a[j] - a[i] == m:
ans += k - j
i += 1
elif a[j] - a[i] > m and j < k:
j += 1
else:
i += 1
print(ans)
Unique Snowflakes - Virtual Judge
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
# 三数之和
class Solution:
def threeSum(self, nums):
nums.sort()
res = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
j, k = i + 1, len(nums) - 1
while j < k:
if nums[i] + nums[j] + nums[k] == 0:
res.append([nums[i], nums[j], nums[k]])
# 去重
while j < k and nums[j] == nums[j + 1]:
j += 1
while j < k and nums[k] == nums[k - 1]:
k -= 1
j += 1
k -= 1
else:
if nums[i] + nums[j] + nums[k] < 0:
j += 1
else:
k -= 1
return res
2.3 二分法
2.3.1 二分法的理论背景
方程求根可以使用二分法，二分法是一种简单高效的方法。
在算法竞赛中有两种题型：整数二分和实数二分。整数域上的二分法要注意数组边界、左右区间的开闭情况，避免漏掉答案或陷入死循环；实数域的二分法要注意精度问题。
2.3.2 整数二分
- 在单调递增序列中找x或x的后继
// 二分查找，查找x或x的后继
int binarySearch(int a[], int n, int x) //a[]必须为单调递增
{
int left = 0, right = n;
while (left < right)
{
int mid = (left + right) / 2;
if (a[mid] >= x)
{
right = mid;
}
else
{
left = mid + 1;
}
}
return left;
}
mid计算有很多方式，如下表：
| 实现 | 使用场合 | 可能出现的问题 |
|---|---|---|
| mid=(left+right)/2 | left>=0，right>=0，left+right无溢出 | (1) left+right可能溢出;(2)负数情况有向0取整的问题 |
| mid=left+(left-right)/2 | left-right无溢出 | 若right和left都是大数且一正一负，right-left可能溢出 |
| mid=left+(left-right)>>1 | left+right无溢出 | 若right和left都是大数，right+left可能溢出 |
总和来说mid=left+(left-right)>>1更好一些。
- 在单调递增序列找x或x的前驱
#include <iostream>
using namespace std;
// 二分查找，查找x或x的前驱
int binarySearch(int a[], int n, int x)
{
int left = 0, right = n;
while (left < right)
{
int mid = (left + right + 1) >> 1;
if (a[mid] <= x)
{
left = mid;
}
else
{
right = mid - 1;
}
}
return left;
}
下面回顾一个简单例题：
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
这是前面出现过的一道例题，下面使用二分法来完成：
首先对数组从小到大排序，复杂度为O(n\log_2n);然后，从头到尾处理数组中的每个元素a[i],在a[i]后面的数中二分查找是否存在一个等于m一a[i]的数，这一步的复杂度也是O(n\log_2n)。两部分相加，总复杂度仍然是O(n\log_2n)。
整数二分经典模型：最大值最小化、最小值最大化。
- 最大值最小化
序列划分
问题描述：例如，有一个序列\{2,2,3,4,5,1\}，将其划分成3个连续的子序列S_1、S_2、S_3,每个子序列最少有一个元素，要求使每个子序列的和的最大值最小。下面举例两种分法。
分法1：S_1、S_2、S_3分别为(2,2,3)、(4,5)、(1)，子序列和分别为7、9、1，最大值为9。
分法2：S_1、S_2、S_3分别为(2,2,3)、(4)、(5,1)，子序列和分别为7、4、6，最大值为7。可见分法2更好。
- 选取一个搜索范围[max,sum] ，max即输入数组的最大值,sum即数组所有元素的和。
- 在这个范围内进行二分法，每次把范围的中间值当作列表分段后，每段和的最大值。
- 然后按照mid值给数组截段，判断数组是否能够被分为m个部分。如果段数大于m，说明每段和太小，增大下界；如果段数小于或等于m，说明每段和太大，减小上界。直到段数等于m就是最终的答案。
# 序列划分
def partition(a, m, mid):
cut = 1
s = 0
res = []
left = 0
for i in range(len(a)):
if s + a[i] <= mid:
s += a[i]
else:
res.append(a[left:i])
left = i
cut += 1
s = a[i]
res.append(a[left:])
if cut == m:
return ['Yes', res]
elif cut > m:
return ['big', res]
elif cut < m:
return ['small', res]
m = int(input()) # 输入需要划分的个数
a = list(map(int, input().split())) # 输入序列
left, right = max(a), sum(a)
while left < right:
mid = right + (left - right) // 2
judge = partition(a, m, mid)
if judge[0] == 'big':
left = mid + 1
elif judge[0] == 'small' or 'Yes':
right = mid
print(partition(a, m, left)[1])
- 最小值最大化
这道题的搜索范围是[0，max]，max是牛棚距离最大的位置。对这个范围进行二分搜索。
检查时把第1头牛放在第1号牛棚，其余至少隔mid放一头牛。如果能放下则加大mid，放不下则减小mid。最终搜索的结果就是最大值。
# 洛谷P1824
def check(mid):
cnt = 1
place = 0
for i in range(1, n):
if x[i] - x[place] >= mid:
place = i
cnt += 1
return cnt >= c
n, c = map(int, input().split())
x = []
for _ in range(n):
x.append(int(input()))
x.sort()
left, right = 0, x[n - 1] - x[0]
ans = 0
while left < right:
mid = (left + right) // 2
if check(mid):
ans = mid
left = mid + 1
else:
right = mid
print(ans)
2.3.3 实数二分
实数二分没有整数二分的取整问题，编码比整数二分简单。
在实数二分中会遇到精度的问题，精度太高会导致超时，精度太低会输出错误答案。平常使用for循环100次左右就可以输出正确答案了。
#include <stdio.h>
#include <math.h>
#include <iostream>
using namespace std;
double PI = acos(-1.0);
double area[10010];
int n, m;
bool check(double mid)
{
int sum = 0;
for (int i = 0; i < n; i++)
sum += (int)(area[i] / mid);
if (sum >= m)
return true;
else
return false;
}
int main()
{
int T;
cin >> T;
while (T--)
{
cin >> n >> m;
m++;
double maxx = 0;
for (int i = 0; i < n; i++)
{
int r;
cin >> r;
area[i] = PI * r * r;
if (area[i] > maxx)
maxx = area[i];
}
double left = 0, right = maxx;
for (int i = 0; i < 100; i++)
{
double mid = (left + right) / 2;
if (check(mid))
left = mid;
else
right = mid;
}
printf("%.4f\n", left);
}
return 0;
}`
习题
2.4 三分法
2.4.1 三分法的概念
如何求解一个单峰（单谷）函数的最大值（最小值）？
- 先确定一个边界[L,R]，确定两点
mid1,mid2。
- 如果
mid1对应的值小于mid2对应的值，将左边界更新至mid1，重新生成mid1。
- 如果
mid2对应的值小于mid1对应的值，将右边界更新至mid2，重新生成mid2。
- 如此循环往复，就能找到单峰函数的最大值。
如何取mid1和mid2呢？
- 三等分，最简单粗暴的做法。
- 近似二等分，取范围中点，让mid1等于中点减精度，mid2等于中点加精度。虽然这种方法可能比上一种方法快一点，但是精度太小会导致两值算出结果相等而判断错方向。
在一般程序中，我们使用第一种方法。
2.4.2 实数三分
#include <bits/stdc++.h>
using namespace std;
int n;
double a[15];
double f(double x)
{
double s = 0;
for (int i = 0; i < n + 1; i++)
s = s * x + a[i];
return s;
}
int main()
{
double L, R;
cin >> n >> L >> R;
for (int i = 0; i < n + 1; i++)
cin >> a[i];
for (int i = 0; i < 100; i++)
{
double k = (R - L) / 3.0;
double mid1 = L + k;
double mid2 = R - k;
if (f(mid1) > f(mid2))
R = mid2;
else
L = mid1;
}
printf("%.5f\n", R);
return 0;
}
n, L, R = list(map(float, input().split()))
a = list(map(float, input().split()))
def f(x):
s = 0
for i in range(int(n) + 1):
s = s * x + a[i]
return s
for _ in range(100):
k = (R - L) / 3.0
mid1 = L + k
mid2 = R - k
if f(mid1) > f(mid2):
R = mid2
else:
L = mid1
print("%.5f" % L)
2.4.3 整数三分
while (right - left > 2)
{
int mid1 = (left + left + right) / 3;
int mid2 = (left + right + right) / 3;
if (f(mid1) < f(mid2))
right = mid2;
else
left = mid1;
}
首先证明不愉快度是时间的下凸函数，可以用三分法求极小值。
// 洛谷P3745
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
int n, m, t[N], b[N];
ll A, B, C, ans;
ll calc1(int p) // 计算通过A,B操作把时间调到p的不愉快度
{
ll x = 0, y = 0;
for (int i = 1; i <= m; i++)
{
if (b[i] < p) // 从左往右
x += p - b[i];
else
y += b[i] - p; // 从右往左
}
if (A < B)
return min(x, y) * A + (y - min(x, y)) * B;
else
return y * B;
}
ll calc2(int p) // 计算学生们的不愉快度总和
{
ll sum = 0;
for (int i = 1; i <= n; i++)
if (t[i] < p)
sum += (p - t[i]) * C;
return sum;
}
int main()
{
cin >> A >> B >> C >> n >> m;
for (int i = 1; i <= n; i++)
cin >> t[i];
for (int i = 1; i <= m; i++)
cin >> b[i];
sort(t + 1, t + n + 1);
sort(b + 1, b + m + 1);
if (C >= 1e16)
{
cout << calc1(t[1]) << endl;
return 0;
}
ans = 1e16;
int l = 1, r = N;
while (r - l > 2)
{
int mid1 = (l + l + r) / 3;
int mid2 = (l + r + r) / 3;
ll c1 = calc1(mid1) + calc2(mid1);
ll c2 = calc1(mid2) + calc2(mid2);
if (c1 < c2)
r = mid2;
else
l = mid1;
}
for (int i = l; i <= r; i++)
{
ll x = calc1(i) + calc2(i);
ans = min(ans, x);
}
cout << ans << endl;
return 0;
}
练习题：
2.5 倍增法和ST算法
倍增法和二分法可以看作相反的算法。二分法是每次缩小一半，从而以O(\log_2n)的速度极快的定位到解。倍增法是每次扩大一倍，以O(2^n )的速度极快的扩展到极大的空间。
倍增法有两种应用场合：
- 在区间问题中，从小区间倍增到大区间，求解和区间查询有关的问题，如求解区间的最大值或最小值。应用有ST算法、后缀数组等。
- 除了区间上的应用，倍增法还可以用于数值的精确计算。如果空间内的元素满足倍增关系，那么也可以用倍增法来求解这些元素的精确值。应用有快速幂、最近公共祖先等。
2.5.1 倍增法
一个整数n,它的二进制只有\log_2n位。如果要从0增长到n,可以以1,2,4,…，2^k为“跳板”，快速跳到n,这些跳板只有\log_2n个。
倍增法的局限性是需要提前计算出第1,2,4,...,2^k个跳板，这要求数据是静态不变的，不是动态变化的。如果数据发生了变化，那么所有跳板需要重新计算，跳板就失去了意义。
倍增法的局限性是需要提前计算出第1,2,4,…,2^k个跳板，这要求数据是静态不变的，不是动态变化的。如果数据发生了变化，那么所有跳板需要重新计算，跳板就失去了意义。
下面给出一道倍增的经典题目：
这道题目最容易想到的做法就是贪心法：
首先考虑从一个区间出发，下一个区间必须与该区间重合，而最优的区间是这些待选区间的右端最大的区间。选定区间完成后，我们再次进行查找，这样找下去就得到了所需的最小区间。
然后我们利用倍增法预计算一些信息，使用go[s][i]定义为走从s出发，走2^i最优区间后到达的区间。计算go[][]可以用下面的计算关系式：go[s][i] = go[go[s][i-1]][i-1]
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 1;
int n, m;
struct warrior
{
int id, L, R; // id:战士的编号；L、R，战士的左右区间
bool operator<(const warrior b) const { return L < b.L; }
} w[N * 2];
int n2;
int go[N][20];
void init()
{ // 贪心 + 预计算倍增
int nxt = 1;
for (int i = 1; i <= n2; i++)
{ // 用贪心求每个区间的下一个区间
while (nxt <= n2 && w[nxt].L <= w[i].R)
nxt++; // 每个区间的下一个是右端点最大的那个区间
go[i][0] = nxt - 1; // 区间i的下一个区间
}
for (int i = 1; (1 << i) <= n; ++i) // 倍增：i=1,2,4,8,... 共log(n)次
for (int s = 1; s <= n2; s++) // 每个区间后的第2^i个区间
go[s][i] = go[go[s][i - 1]][i - 1];
}
int res[N];
void getans(int x)
{ // 从第x个战士出发
int len = w[x].L + m, cur = x, ans = 1;
for (int i = log2(N); i >= 0; i--)
{ // 从最大的i开始找：2^i = N
int pos = go[cur][i];
if (pos && w[pos].R < len)
{
ans += 1 << i; // 累加跳过的区
cur = pos; // 从新位置继续开始
}
}
res[w[x].id] = ans + 1;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
w[i].id = i; // 记录战士的顺序
scanf("%d%d", &w[i].L, &w[i].R);
if (w[i].R < w[i].L)
w[i].R += m; // 把环变成链
}
sort(w + 1, w + n + 1); // 按左端点排序
n2 = n;
for (int i = 1; i <= n; i++) // 拆环加倍成一条链
{
n2++;
w[n2] = w[i];
w[n2].L = w[i].L + m;
w[n2].R = w[i].R + m;
}
init();
for (int i = 1; i <= n; i++)
getans(i); // 逐个计算每个战士
for (int i = 1; i <= n; i++)
printf("%d ", res[i]);
return 0;
}
2.5.2 ST算法
ST算法基于倍增原理，适用于静态空间的RMQ问题：给定长度为n的静态数列，做m次查询，每次给定L,R\le n，求解数列区间内[L,R]的最值。
我们知道一个区间的每一个子区间都含有最大值和最小值，而父区间的最大值就是各个子区间最大值的最大值。如何实现高效的算法，可以用下面的例子：
- 分组，第i组有n个小区间，每个区间的元素有i个，这样分下去共有\log_2n组。
- 定义dp[s][k]为左端点是s，区间长度为2^k的区间最值，有这样的递推关系：dp[s][i]=min/max{dp[s][k-1],dp[s+1<<(k-1)][k-1]}
计算每个小区间的最值的时间复杂度为O(n\log_2n)。
如何查询任意区间的最值呢？令len=R-L+1，区间长度x为比len小的2的最大倍数，这样能保证覆盖：
2^k=x，可以计算出k
区间[L,R]的最值计算公式：min/max{dp[L][k],dp[R-(1<<k)+1][k]}，下面给出一道例题：
[USACO07JAN] Balanced Lineup G - 洛谷
# 洛谷p2880
import math
n, q = map(int, input().split())
h = []
for i in range(n):
h.append(int(input()))
l = []
for i in range(q):
l.append(list(map(int, input().split())))
dp_max = [[0 for i in range(n+1)] for i in range(math.ceil(math.log2(n)))]
dp_min = [[0 for i in range(n+1)] for i in range(math.ceil(math.log2(n)))]
dp_max[0][1:] = h
dp_min[0][1:] = h
# 计算dp
for i in range(1, math.ceil(math.log2(n))): # 2^i个数
for j in range(1, n+1): # 从第j个数开始
if j + (1 << i) - 1 <= n:
k = (1 << (i-1))
dp_max[i][j] = max(dp_max[i-1][j], dp_max[i-1][j+k])
dp_min[i][j] = min(dp_min[i-1][j], dp_min[i-1][j+k])
else:
break
# 计算答案
for i in range(q):
l1 = l[i][0]
l2 = l[i][1]
k = math.floor(math.log2(l2-l1+1))
print(max(dp_max[k][l1], dp_max[k][l2-(1 << k)+1]) -
min(dp_min[k][l1], dp_min[k][l2-(1 << k)+1]))
2.6 前缀和与差分
2.6.1 一维差分
差分数组的定义为D[k]=a[k]-a[k-1]，因此可以推出a[k]=D[1]+D[2]+…+D[k]，也就是D的前缀和。于是可以得到差分是前缀和的逆运算。使用差分能很好的记录区间的修改，下面来看一道例子：
// hud 1556
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N], D[N];
int main()
{
int n;
while (~scanf("%d", &n))
{
memset(D, 0, sizeof(D));
memset(a, 0, sizeof(a));
for (int i = 1; i <= n; i++)
{
int L, R;
scanf("%d%d", &L, &R);
D[L]++;
D[R + 1]--;
}
for (int i = 1; i <= n; i++)
{
a[i] = a[i - 1] + D[i];
if (i != n)
printf("%d ", a[i]);
else
printf("%d\n", a[i]);
}
}
return 0;
}
评论区