【算法笔记】基础算法

0.基础

0.1.除法上取整：取比自己大的最小整数

int x = 9;
int divisor = 3;
// (9 + 3 - 1) / 3 = 3
int res = (x + divisor - 1) / divisor;

int x = 7;
int divisor = 3;
// (7 + 3 - 1) / 3 = 3
int res = (x + divisor - 1) / divisor;

也可以使用 C++ 中的 ceil() 函数

int x = 7;
int divisor = 3;
int res = ceil(x / divisor);

0.2.除法下取整：取比自己小的最大整数

int x = 9;
int divisor = 3;
// 9 / 3 = 3
int res = x / divisor;

int x = 7;
int divisor = 3;
// 7 / 3 = 2
int res = x / divisor;

也可以使用 C++ 中的 floor() 函数

int x = 7;
int divisor = 3;
int res = floor(x / divisor);

1.排序算法

1.1.快速排序

https://www.bilibili.com/video/BV17h4y1E73i/?spm_id_from=333.1387.search.video_card.click&vd_source=23924d35b21e0613a415b27939e67698

分治思想，先交换后拆分，时间复杂度O(nlogn)。

#include <iostream>
using namespace std;
const int N = 1e6 + 10;

int n;
int q[N];

void quick_sort(int q[], int l, int r) //*q也是正确的
{
    if (l >= r) return;  //判断边界，当然l == r也是可以的，看个人习惯

    int x = q[(l + r) / 2], i = l - 1, j = r + 1; //取分界点
    while (i < j)
    {
        do i++ ; while (q[i] < x);//向右找>=x的数
        do j-- ; while (q[j] > x);//向左找<=x的数
        if (i < j) swap(q[i], q[j]);
        /*swap函数等效
        if (i < j)
        {
            int t = q[i];
            q[i] = q[j];
            q[j] = t;
        }
        */
    }

    quick_sort(q, l, j); //当然换成i-1也是可以的，但是更换成i-1之后要注意x的取值不能是q[l](j时x不能取q[r])，会出现死循环
    quick_sort(q, j + 1, r);
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &q[i]);
    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n; i++) printf("%d ", q[i]);

    return 0;
}

• 退出while时，i=j或者i=j+1
• 相同元素的顺序可能会交换，是不保序的（不稳定的）

1.1.2.第k个小的数字

int n,k,a[100010];

int qnth_element(int l, int r){
    if(l==r) return a[l];
    int i=l-1, j=r+1, x=a[(l+r)/2];
    while(i<j){
        do i++; while(a[i]<x); //向右找>=x的数
        do j--; while(a[j]>x); //向左找<=x的数
        if(i<j) swap(a[i],a[j]);
    }
    if(k<=j) return qnth_element(l,j);
    else return qnth_element(j+1,r);
}

1.2.归并排序

https://www.bilibili.com/video/BV1Mx4y1o7B1/?spm_id_from=333.1387.search.video_card.click&vd_source=23924d35b21e0613a415b27939e67698

分治思想，先拆分后合并，时间复杂度O(nlogn)。

#include<iostream>
using namespace std;
const int N = 100010;
int n;
int q[N], tmp[N];

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];
    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
    merge_sort(q, 0, n - 1);
    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
    return 0;
}

• 是稳定的

易错点

• 注意边界i=l而不是i=0
• 注意函数名的定义sort() 这个函数和 std::sort() 冲突

1.2.2.逆序对个数

int n,a[500010],b[500010];
long long res;

void merge(int l,int r){
    if(l>=r) return;
    int mid=l+r>>1;
    merge(l,mid);
    merge(mid+1,r); 

    int i=l,j=mid+1,k=l; 
    while(i<=mid && j<=r){
        if(a[i]<=a[j]) b[k++]=a[i++];
        else b[k++]=a[j++], res+=mid-i+1; //这里多了一个统计，每当从右段取数字时，统计逆序对的数目
    }
    while(i<=mid) b[k++]=a[i++];
    while(j<=r) b[k++]=a[j++];
    for(i=l; i<=r; i++) a[i]=b[i];
}

2.二分查找

2.1.整数二分

（很多边界问题，容易死循环，背模板）

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}

// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) r = mid - 1 ;  //比如：mid>=某个数
        else l = mid;
    }
    return l;
}

2.2.浮点数二分

（不会存在任何边界问题，好写）

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)  //或者直接循环一定次数，不用显式设置精度要求。例如：for(int i=0;i<100;i++)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

• 可应用于求平方根（有精度要求的平方根），例如

  #include<iostream>
  
  using namespace std;
  
  int main() {
      double a;
      scanf("%lf", &a);
      double l = 0, r = a;
      while ((r - l) > 1e-8) {
          double mid = (l + r) / 2;
          if (a <= mid * mid)r = mid;
          else l = mid;
      }
      printf("%lf", l);
      return 0;
  }

3.高精度

3.1.高精度加法

#include <iostream>
#include <vector>
using namespace std;

// C = A + B
vector<int> add(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || i < B.size(); i ++ )
    {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if (t) C.push_back(t);
    return C;
}
int main()
{
    string a, b;
    vector<int> A, B;

    cin >> a >> b; // a = "123456"
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0'); // A = [6, 5, 4, 3, 2, 1]
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');

    auto C = add(A, B); // 等价于vector<int> C = add(A, B);

    for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);
    return 0;
}

或者

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

3.2.高精度减法

#include <iostream>
#include <vector>

using namespace std;

// 判断是否有 A >= B
bool cmp(vector<int> &A, vector<int> &B) {
    if (A.size() != B.size()) return A.size() > B.size();
    for (int i = A.size() - 1; i >= 0; i--)
        if (A[i] != B[i])
            return A[i] > B[i];
    return true;
}

// C = A - B
vector<int> sub(vector<int> &A, vector<int> &B) {
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i++) {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    // 如果条件为C.size()>0，虽然实现“形如003pop掉前两个0”的效果但是对于答案是0的情况下就会出错
    // C.size()>1则保留至少一个元素（即不会移除全部元素）
    return C;
}

int main() {
    string a, b;
    vector<int> A, B;

    cin >> a >> b; // a = "123456"
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0'); // A = [6, 5, 4, 3, 2, 1]
    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');

    if (cmp(A, B)) {
        auto C = sub(A, B);
        for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    } else {
        auto C = sub(B, A);
        printf("-");
        for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    }
    return 0;
}

或者

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

3.3.高精度乘法

// C = A * b, A >= 0, b >= 0, len(A) <= 1e6, b <= 1e6
#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int> &A, int b) {
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i++) {  
      	// 注意t非0则需要继续循环，可能会出现进大于一位数的情况（例如：2*120=240，进位为24）
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    return C;
}

int main() {
    string a;
    int b;
    cin >> a >> b;

    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');

    auto C = mul(A, b);

    for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);

    return 0;
}

或者

// C = A * b, A >= 0, b >= 0, len(A) <= 1e6, b <= 1e6
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

3.4.高精度除法

// A / b = C ... r, A >= 0, b > 0, len(A) <= 1e6, b <= 1e6
#include <iostream>
#include<algorithm>
#include <vector>

using namespace std;

vector<int> div(vector<int> &A, int b, int &r) {
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i--) {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main() {
    string a;
    int b;
    cin >> a >> b;

    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');

    int r;
    auto C = div(A, b, r);

    for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
    cout << endl << r << endl;

    return 0;
}

或者

// A / b = C ... r, A >= 0, b > 0, len(A) <= 1e6, b <= 1e6
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

4.前缀和与差分

4.1.一维前缀和

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

#include <iostream>
using namespace std;

const int N = 100010;

int n, m;
int a[N], s[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); 

    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];

    while (m -- )
    {
        int l, r;
        scanf("%d %d", &l, &r);
      	// 数据输入量大的时候建议用scanf，scanf比cin快一倍。
      	// 当然也可以用ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);关闭同步/解除绑定
        printf("%d\n", s[r] - s[l - 1]);
    }

    return 0;
}

4.2.二维前缀和

S[i, j] = 第i行j列格子左上部分所有元素的和
// 以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

#include <iostream>
const int N = 1010;

int n, m, q;
int a[N][N], s[N][N];

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]; // 求前缀和

    while (q--)
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]); // 算部分和
    }

    return 0;
}

4.3.一维差分

前缀和的逆运算

// 给区间[l, r]中的每个数加上c：
B[l] += c, B[r + 1] -= c

4.3.1.示例代码

#include <iostream>
using namespace std;
const int N = 100010;

int n, m;
int a[N], b[N];

void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) insert(i, i, a[i]); // 初始插入，初始化差分矩阵的前缀和

    while (m -- )
    {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }

    for (int i = 1; i <= n; i ++ ) b[i] += b[i - 1];

    for (int i = 1; i <= n; i ++ ) printf("%d ", b[i]);

    return 0;
}

4.4.二维差分

// 给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

4.4.1.示例代码

#include <iostream>
using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], b[N][N];

void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}
int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &a[i][j]);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            insert(i, j, i, j, a[i][j]);

    while (q -- )
    {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];

    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ ) printf("%d ", b[i][j]);
        puts("");
    }

    return 0;
}

5.双指针算法

归并排序也是一个双指针算法

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}

常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

核心思想：

for (int i = 0; i < n; i ++ ){
   for (int j = 0; j < n; j ++ ){
      
    }
}

将上面的朴素算法（时间复杂度为 O(n^2)）优化到O(n)

5.1.示例代码

题目：输入一个字符串，请你把每一个单词单独输出并每个单词占单独一行

例如，输入“An apple a day, keeps the doctor away.”，

输出：

​ An

​ apple

​ ……

#include <iostream>
#include <string.h>

using namespace std;

int main() {
    char str[1000];
    gets(str);
    int n = strlen(str);

    for (int i = 0; i < n; i++) {
        int j = i;
        while (j < n && str[j] != ' ') j++;
        // 这道题的具体逻辑
        for (int k = i; k < j; k++) cout << str[k];
        cout << endl;
        i = j;
    }
    return 0;
}

5.2.示例代码

最长连续不重复子序列

给定一个长度为n的整数序列，请找出最长的不包含重复数字的连续子序列，输出它的长度。

输入格式

• 第一行包含整数n。
• 第二行包含n个整数（均在0~100000范围内），表示整数序列。

输出格式

• 共一行，包含一个整数，表示最长的不包含重复数字的连续子序列的长度。

数据范围：1 ≤ n ≤ 100000

输入样例：
5
1 2 2 3 5

输出样例：
3

#include <iostream>
using namespace std;
const int N = 100010;

int n;
int a[N], s[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    int res = 0;
    for (int i = 0, j = 0; i < n; i ++ )
    {
        s[a[i]] ++ ;
        while (s[a[i]] > 1)
        {
            s[a[j]] -- ;
            j ++ ;
        }
        res = max(res, i - j + 1);
    }
    cout << res << endl;

    return 0;
}

6.位运算

6.1.求n的第k位数字:

n >> k & 1

• 先把第k位移动到最后一位，右移k位

• 然后只要求得到k位的话，与1做与运算

6.2.返回n的最后一位1

lowbit(n) = n & -n（二进制的负数是原数的补码，也就是取反加一，即`-n=~n+1`）

提取 x 的最低有效位（Least Significant Bit, LSB）中为 1 的那一位

• （101000）返回（1000）

6.3.示例代码

二进制中1的个数

给定一个长度为n的数列，请你求出数列中每个数的二进制表示中1的个数。

输入格式

• 第一行包含整数n。
• 第二行包含n个整数，表示整个数列。

输出格式

• 共一行，包含n个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中1的个数。

数据范围

• 1 ≤ n ≤ 100000，
• 0 ≤ 数列中元素的值 ≤ 10^9

输入样例：
3
1 2 3 4 5

输出样例：
1 1 2 1 2

#include <iostream>

using namespace std;

int lowbit(int x) {
    return x & -x;
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;

        int res = 0;
        while (x) x -= lowbit(x), res++; // 每次减去x的最后一位1

        cout << res << endl;
    }
    return 0;
}

7.离散化

常用情况：数值的范围很大，但是数的个数远小于数的值（值域跨度很大，但是很稀疏）

vector<int> alls; // 存储所有待离散化（保序离散化）的值
// 排序 + 去重
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

############ unique函数的实现 ###############
vector<int>::iterator unique(vector<int> &a)
{
    int j = 0;
    for (int i = 0; i < a.size(); i ++ )
        if (!i || a[i] != a[i - 1])
            a[j ++ ] = a[i];
    // a[0] ~ a[j - 1] 所有a中不重复的数

    return a.begin() + j;
}
##########################################3

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n，不加1的话映射到0,1,2,……
}

7.1.示例代码（前缀和+离散化）

802. 区间和

假定有一个无限长的数轴，数轴上每个坐标上的数都是0。现在，我们首先进行 n 次操作，每次操作将某一位置x上的数加c。近下来，进行 m 次询问，每个询问包含两个整数l和r，你需要求出在区间[l, r]之间的所有数的和。

输入格式

• 第一行包含两个整数n和m。

• 接下来 n 行，每行包含两个整数x和c。

• 再接下里 m 行，每行包含两个整数l和r。

输出格式

• 共m行，每行输出一个询问中所求的区间内数字和。

数据范围

• -10^9 ≤ x ≤ 10^9,（数值的范围很大，但是数的个数远小于数的值）

• 1 ≤ n,m ≤ 10^5,

• -10^9 ≤ l ≤ r ≤ 10^9,

• -10000 ≤ c ≤ 10000

输入样例：
3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例：
8
0
5

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
int n, m;
int a[N], s[N];
vector<int> alls;
vector<PII> add, query;

int find(int x) {
    int l = 0, r = alls.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});
        alls.push_back(x);
    }
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});

        alls.push_back(l);
        alls.push_back(r);
    }

// 去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

// 处理插入
    for (auto item: add) {
        int x = find(item.first);
        a[x] += item.second;
    }

// 预处理前缀和
    for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];

// 处理询问
    for (auto item: query) {
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}

8.区间合并

// 将所有存在交集的区间合并
void merge(vector <PII> &segs) {
    vector <PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;
    for (auto seg: segs)
        if (ed < seg.first) {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        } else ed = max(ed, seg.second);

    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}

8.1. 完整代码：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
int n;
vector<PII> segs;

void merge(vector <PII> &segs) {
    vector <PII> res;
    sort(segs.begin(), segs.end()); // 先以第一个参数为排序关键字，再以第二个为关键字

  	int st = -2e9, ed = -2e9;
    for (auto seg: segs)
        if (ed < seg.first) {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        } else ed = max(ed, seg.second);

    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }
    merge(segs);
    cout << segs.size() << endl;
    return 0;
}

本文转载整理信息如下

• 链接：https://www.acwing.com/blog/content/277/
• 参考来源：AcWing