前言
尝试用最朴素的语言，将问题阐释清楚。
算法实验6：最大子段和（四种做法）
题目： 最大子段和
题意：
给定有n个整数(可能为负整数)组成的序列a1,a2,…,an,求该序列连续的子段和的最大值。 如果该子段的所有元素和是负整数时定义其最大子段和为0。
输入格式
第一行有一个正整数n(n<1000)，后面跟n个整数,绝对值都小于10000。直到文件结束。
输出格式
输出它的最大子段和。
数据范围
n<1000
输入样例：
6 -2 11 -4 13 -5 -2输出样例：
20要求：
分别用普通O(n3)或O(n2)、分治O(nlogn)和动态规划O(n)实现。
思路：
-
普通O(n3)。由于所要寻找的子段是连续的，那么我们可以遍历每个起点，对于每个起点遍历其所有终点，然后对于找到所有子段维护一个最大值即可。
- 遍历起点需要一个循环，对于每个起点遍历终点需要一个循环，而找到起点和终点后，我们还需要遍历这一段子段来求其总和，共三重循环，时间复杂度为O(n3)。
-
O(n2)。考虑如何优化上述的三重循环，显然找起点和终点的循环是不太好优化的，那么第三重循环是否可以优化呢？
- 重新审视一下我们 第三重循环的作用：遍历起点为i，终点为j的子段求其总和 。再看 第二重循环的作用：对于每个起点，遍历其所有终点（注意体会） 。对比两个循环的作用，我们会发现当我们在进行第三重循环的时候，实际上是在执行第二重循环已经执行过的事情。这造成了大量无意义的循环浪费。只要我们能在第二重循环直接求出起点为i，终点为j的子段的总和，就可以直接去掉第三重循环。
- 那么优化就很简单了，直接将第三重循环去掉，用
sum记录起点为i终点为j的子段，在第二重循环中，每让sum加一次，就维护一次最大值即可。两重循环，时间复杂度为O(n2)。
-
分治O(nlogn)。好消息：分治一般用递归写，递归写法一般都很简单。坏消息：不会写递归。
- 让我们再回忆一下分治的思想：将大问题分解为小问题，直到小问题可以直接解决，然后从小到大最终将问题解决。考虑如何用分治思想去做？如果只有2个数，我们可以直接得到子段的最大值吗？可以。如果只有一个数可以吗？可以。我们会发现，问题的规模越小越容易得到答案。
- 那么分治的思路就出来了，我们可以将序列一分为二，先找左边子段最大值，然后找出右边子段最大值，最后比较左右两边子段最大值谁更大就好了。考虑一个问题，子段的起点和终点总是在一侧？显然不是。此时还有一种情况我们没有考虑到，如果某个子段起点在左边，终点在右边呢？很简单，我们只需要从序列分割点开始，分别向左和向右开始遍历，找到起点为分割点终点在左边的最大值和起点为分割点终点在右边的最大值，然后将两个值相加就是起点与终点在不同侧的最大值。
- 此时我们得到了三个值：起点和终点都在左边的最大值，起点和终点都在右边的最大值，起点和终点在不同侧的最大值。比较三者得到最后的答案。什么，你问我递归在哪？让我考考你，我们如何求左边和右边的最大值呢？交给递归就好啦hhh。
-
动态规划O(n)。动态规划的代码一般很简单，但是递推方程不太好想。
-
考虑找n个数的最大子段和的子问题是什么？显然，是找n-1个数的最大子段和。找n-1个数的呢？那就是找n-2个数。一直找下去，直到找1个数的最大子段和。而1个数的最大子段和显然就是它自己。我们找到了1个数的最大字段和，那么求2个数最大子段和的时候就很简单了，如果第1个数小于0，那么2个数的最大子段和就是第2个数，否则就是第2个数加第1个数。
-
将上述思路延伸之后：每次都在序列后面加一个数，然后判断前面n-1个数的最大子段和是否大于0，如果大于0，n个数的最大子段和就是前n-1个数的最大子段和加第n个数，否则就只有第n个数。这样做是否可以保证正确性呢？很遗憾是否定的。因为这样我们无法保证子段是连续的，例如前4个的最大子段和是第1个数和第2个数的和，那么第五个数就不能直接加在前4个的最大子段和上。怎么办
-
其实很简单，我们可以用
f[i]来表示以第i个数结尾的所有子段和中的最大值。那么就可以得到递推公式：
$$
f[i]=(f[i-1]>0?f[i-1]+a[i]:a[i]);
$$
-
-
因为
f[i]是以位置i为终点的所有子段的最大值，所以一定包含a[i]。考虑如果f[i-1]>0，f[i]和f[i-1]的关系。显然，f[i]一定包含f[i-1]。因为此时一定有：f[i-1]+a[i]>a[i]。而如果f[i-1]<0，那么f[i]显然不包含f[i-1]更好。
普通O(n3)代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
typedef long long ll;
int a[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
ll mm=0;
//遍历起点
for(int i=1;i<=n;++i)
{
//对于每个起点遍历终点
for(int j=i;j<=n;++j)
{
ll sum=0;
//遍历起点为i，终点为j的子段，sum为其总和
for(int k=i;k<=j;++k)sum+=(ll)a[k];
//mm维护所有子段的最大值
mm=max(sum,mm);
}
}
mm>0?cout<<mm:cout<<0;
//system("pause");
return 0;
}O(n2)代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
typedef long long ll;
int a[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
ll mm=0;
for(int i=1;i<=n;++i)
{
ll sum=0;
//对于每个起点，找到所有终点，就已经遍历了所有可能
for(int j=i;j<=n;++j)
{
sum+=a[j];
mm=max(mm,sum);
}
}
mm>0?cout<<mm:cout<<0;
//system("pause");
return 0;
}分治O(nlogn)代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
typedef long long ll;
int a[N];
ll slove(int l,int r)
{
if(l==r)return a[r]>0?a[r]:0;
int m=l+r>>1;
ll lm=slove(l,m);//首尾均在左边的最大值
ll rm=slove(m+1,r);//首尾均在右边的最大值
lm=max(lm,rm);
//首尾在两侧的最大值
ll mm=0,resl=0,resr=0;
for(int i=m;i>=l;--i)
{
mm+=(ll)a[i];
resl=max(resl,mm);
}
mm=0;//
for(int i=m+1;i<=r;++i)
{
mm+=(ll)a[i];
resr=max(resr,mm);
}
ll res=resr+resl;
res=max(lm,res);
return res>0?res:0;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
ll ans=slove(1,n);
cout<<ans;
//system("pause");
return 0;
}动态规划O(n)代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
typedef long long ll;
//f[i]表示以位置i为结尾的最大字段和
ll a[N],f[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
//初始化，以第一个数为终点的子段值一定为a[1]
f[1]=a[1];
for(int i=2;i<=n;++i)
f[i]=(f[i-1]>0?f[i-1]+a[i]:a[i]);
ll mm=0;
for(int i=1;i<=n;++i)
mm=max(mm,f[i]);
cout<<mm<<endl;
//system("pause");
return 0;
}算法实验7：矩阵连乘
题目： 矩阵连乘
题意：
给你2个矩阵A、B，我们使用标准的矩阵相乘定义C=AB如下： A数组中栏（column）的数目一定要等于B数组中列（row）的数目才可以做此2数组的相乘。若我们以rows(A)，columns(A)分 别代表A数组中列及栏的数目，要计算C数组共需要的乘法的数目为：rows(A)*columns(B)*columns(A)。例如：A数组是一个 10 x 20的矩阵，B数组是个20 x 15的矩阵，那么要算出C数组需要做10 * 15 * 20，也就是3000次乘法。 要计算超过2个以上的矩阵相乘就得决定要用怎样的顺序来做。例如：X、Y、Z都是矩阵，要计算XYZ的话可以有2种选择：(XY)Z 或者 X(YZ)。假设X是5 x 10的数组，Y是10 x 20的数组，Z是20 x 35的数组，那个不同的运算顺序所需的乘法数会有不同： (XY)Z • 5 * 20 * 10 = 1000次乘法完成(XY)，并得到一5x20的数组。 • 5 * 35 * 20 = 3500次乘法得到最后的结果。 • 总共需要的乘法的次数：1000+3500=4500。 X(YZ) • 10 * 35 * 20 = 7000次乘法完成(YZ)，并得到一10 x 35的数组。 • 5 * 35 * 10 = 1750次乘法得到最后的结果。 • 总共需要的乘法的次数：7000+1750=8750。 很明显的，我们可以知道计算(XY)Z会使用较少次的乘法。 这个问题是：给你一些矩阵，你要写一个程序来决定该如何相乘的顺序，使得用到乘法的次数会最少。
输入格式
含有多组测试数据，每组测试数据的第一列，含有1个整数N（N <= 10）代表有多少个数组要相乘。接下来有N对整数，代表一数组的列数及栏数。这N个数组的顺序与要你相乘的数组顺序是一样的。N=0代表输入结束。请参考Sample Input。
输出格式
每组测试数据输出一列，内容为矩阵相乘的顺序（以刮号来表示）使得所用的乘法次数最小。如果有不只一组答案，输出任一组均可。请参考Sample Output。
数据范围
N <= 10
输入样例：
3
1 5
5 20
20 1
3
5 10
10 20
20 35
6
30 35
35 15
15 5
5 10
10 20
20 25
0输出样例：
Case 1: (A1 x (A2 x A3))
Case 2: ((A1 x A2) x A3)
Case 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))思路：
-
朴素思想。给我们n个矩阵，然后问我们什么样的计算顺序可以使得最后的总乘积最小。最简单的思想就是遍历n个矩阵的所有排序，计算出所有排序方式各自的总乘积，维护一个最小值。但这样带来的问题是时间复杂度非常的高。随着n的增大，花费的时间是指数增长的。
-
动态规划。我们将n个矩阵放在水平线上，同时去掉相邻相同的数。例如样例2为：[5,10,50,35]
- 第一步，分析最优解的结构：将矩阵连乘的积AiAi+1…Aj 简记为
A[1:n]，则如果A[1:n]是最优乘积，那么A[1:k](k<=n)一定也是最优的。因为如果有一种更好的次序可以使得A[1:k]乘积更小，那么A[1:n]就一定有乘积更小的排序方式。同理A[k+1:n]也一定是最优的计算次序。 - 第二步，建立递归关系：设
m[i][j]表示：矩阵i到矩阵j乘积最小值。原问题的最优值就是m[1][n]。当i=j时，A[i:j]=A[i]，无需计算，所以计算次数为0。当i<j时，可以利用最优子结构计算m[i][j]。例如，如果A[i:j]的最优次序在Ak和Ak+1之间断开，i<=k<=j，则可得式1：m[i][j]=m[i][k]+m[k+1][j]+pi-1×pk×pj。此时我们还不知道k的位置，但是k的位置只有j-i种可能，所以k∈{i,i+1,…,j-1}。也即k是上述j-i种可能中使得式1计算量最小的那个位置。 - 于是我们可以得到递推公式：当i=j，
m[i][j]=0；当i<j，mini<=k<=j {m[i][k]+m[k+1][j]+pi-1×pk×pj}。 - 第三步，计算最优值。如果我们简单的从上往下进行递归，时间复杂度依然是指数级别，这是因为我们在递归计算时将不同的子问题大量重复计算了。如何保证每个子问题只计算一次？我们可以从下往上进行递归。按照矩阵长度由小到大的进递归计算，这样的方式是自底而上的。
- 如何记录最优次序？我们会发现每次找到的k就是
A[i:j]最优次序的分割点，如果我们能记录下每次k分割哪两部分，我们就能找到最优次序。可以用s[i][j]表示当矩阵i到矩阵j乘积为最小值时，分割点是哪个矩阵。每次找到k值时记录在s[i][j]中，然后递归回溯直接输出就可以了。
- 第一步，分析最优解的结构：将矩阵连乘的积AiAi+1…Aj 简记为
动态规划代码：
#include<bits/stdc++.h>
using namespace std;
const int N=15;
const int INF=0x3f3f3f3f;
typedef long long ll;
int n;
//m[i][j]：矩阵i到矩阵j乘积最小值
//s[i][j]：当矩阵i到矩阵j乘积为最小值时，分割点是哪个矩阵。例如，当s[1][3]=1时，表示1和2断开
int p[N],m[N][N],s[N][N];
//动态规划，找到最优的计算次序
void matrixChain()
{
//当只有一个矩阵时，不需要计算
for(int i=1;i<=n;++i)m[i][i]=0;
//r表示矩阵连乘的长度。例如当r=3时，表示有三个相邻矩阵相乘
for(int r=2;r<=n;++r)
{
//i为当前矩阵连乘的起点
for(int i=1;i<=n-r+1;++i)
{
//j是当前矩阵连乘的终点
int j=i+r-1;
m[i][j]=INT_MAX;
//k遍历[i,j-1]，找到可以使得矩阵i到矩阵j乘积最小的分割点
//为什么k不取j?因为我们规定s[i][j]=u，表示u和u+1断开，所以最多遍历到j-1
for(int k=i;k<j;k++)
{
int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(t<m[i][j])
{
m[i][j]=t;
s[i][j]=k;
}
}
}
}
}
//递归，输出最优的计算次序
void traceback(int i,int j)
{
//s[i][j]表示矩阵i到矩阵j的最佳分割点，当只有一个矩阵时，最佳分割点就是自己
if(i==j)
{
printf("A%d",i);
return ;
}
//递归一目了然：( { i, s[i][j] } x { s[i][j]+1, j } )
cout<<"(";
//输出i到s[i][j]的最佳分割点
traceback(i,s[i][j]);
cout<<" x ";
//输出s[i][j]+1到j的最佳分割点
traceback(s[i][j]+1,j);
//cout<<"multiply A"<<i<<","<<s[i][j]<<"and A"<<s[i][j]+1<<","<<j<<endl;
cout<<")";
}
int main()
{
int CASE=0;
while(cin>>n&&n>0)
{
memset(m,0,sizeof m);
memset(s,0,sizeof s);
cin>>p[0]>>p[1];
for(int i=2;i<=n;++i)
{
int x;
cin>>x>>p[i];
}
matrixChain();
cout<<"Case "<<++CASE<<": ";
traceback(1,n);
cout<<endl;
}
//system("pause");
return 0;
}算法实验8：划分问题
题目： 划分问题
题意：
给定一个正整数的集合A={a1,a2,….,an},是否可以将其分割成两个子集合，使两个子集合的数加起来的和相等。例A = { 1, 3, 8, 4, 10} 可以分割：{1, 8, 4} 及 {3, 10}
输入格式
第一行集合元素个数n（n <=300）， 第二行n个整数。
输出格式
如果能划分成两个集合，输出任意一个子集，否则输出“no”。
数据范围
N <= 300
输入样例：
5
1 3 8 4 10输出样例：
3 10思路：
- 背包问题。由于题目要求我们将所有数都分到两个集合之一中，那么如果所有数的总和是奇数，显然无法得到两个相同值的集合。所以我们可以在输入的时候就计算一下所有数的总和
sum，若sum为奇数，则直接输出no。 - 我们已经知道所有数的总和为
sum，那么问题就转为了是否能找到任意个数，使得它们的值总和刚好为sum/2，如果可以找到，显然这就是其中一种划分方式。而这恰与背包问题相契合。 - 用
bool类型的f[i][j]表示：前i个元素是否可以凑出和为j的值。原问题就转化为求f[n][sum/2]是否为真，如果为真说明是可以找到划分方式的，反之则不可以。当i=1时，只有放与不放第1个数，所以f[1][0]和f[1][a[1]]均为真。当i>1时，如果f[i-1][j]为真，则f[i][j]也为真，不放第i个数就好了。而如果f[i-1][j-a[i]]为真，则f[i][j]也为真，因为此时放入第i个数刚好可以得到f[i][j]。但是后者要注意判断j-a[i]是不能小于0的，因为我们所给定的数均为正整数。 - 如果
f[n][sum/2]为真，如何找到其中一种划分方式？我们可以根据sum/2和f[i][j]的值回溯。- 第i件物品如果放进来了一定符合两个条件：1.前i件物品在当前空间下可以放满。2.前i件物品在不放第i件物品的前提下无法放满当前空间。
- 如欲了解更多背包问题：背包问题模板 | ❤梧桐苑
01背包代码：
#include<bits/stdc++.h>
using namespace std;
const int N=3e2+10;
const int INF=0x3f3f3f3f;
typedef long long ll;
int n;
int a[N];
int main()
{
cin>>n;
int sum=0;
for(int i=1;i<=n;++i)
{
cin>>a[i];
sum+=a[i];
}
if(sum&1)
{
cout<<"no"<<endl;
//system("pause");
return 0;
}
sum/=2;
//f[i][j]为 true表示：前i个元素可以凑出和为j的值
bool f[n+1][sum+1];
memset(f,false,sizeof f);
f[1][0]=f[1][a[1]]=true;
for(int i=2;i<=n;++i)
{
for(int j=0;j<=sum;++j)
{
//将j视为背包空间，a[i]视为物品体积，有点背包的意思
//注意判断条件
if((j-a[i])>=0&&f[i-1][j-a[i]]==true)f[i][j]=f[i-1][j-a[i]];
else f[i][j]=f[i-1][j];
}
}
if(f[n][sum]==false)
{
cout<<"no"<<endl;
//system("pause");
return 0;
}
//往回找，第i件物品如果放进来了一定符合两个条件：
//1.前i件物品在当前空间下可以放满
//2.前i件物品在不放第i件物品的前提下无法放满当前空间
for(int i=n;i>=1;--i)
{
if(sum<=0)break;
if(f[i][sum]&&f[i-1][sum]==false)
{
cout<<a[i]<<" ";
sum-=a[i];
}
}
//system("pause");
return 0;
}算法实验9：背包
题目： 背包
题意：
卖方：这件商品14元
买方：给你20元
卖方：不好意思，我的零钱不够
买方：好吧，这是15元，剩的当小费
当到一个地方旅游时，如果你买东西的地方不支持信用，带零钱还是非常有用的。特别是有时候卖方没有零钱，如果你没有刚好的钱，你需要支付比卖价多一点。
当然你想付尽量少的钱（至少是商品价值的钱）。并且，当支付最少钱的时候，也最好是支付的硬币的数量最少。
输入格式
第一行包含一个整数表示测试数据的组数。每组测试数据每一行包含一个整数，表示你需要付的钱数，钱数不超过10000元。接下来包含一个整数n，表示你所拥有的钱的数量，n最多是100,接下来的n行每行一个整数，表示你有的每个硬币的面值，注意钱的面值可以是任意的，不和我们现在用的面值一样，钱的面值不超过10000元。
输出格式
对每组测试数据，在一行上输出两个整数：需要支付的钱数和数量。
数据范围
目标钱数 <= 10000
n <= 10000
硬币面值 <= 10000
输入样例：
1
1400
3
500
1000
2000输出样例：
1500 2思路：
- 背包问题。01背包的简单变形。考虑将目标钱数视为背包容量，每个硬币的价值是物品体积，那么问题就转化为找到x件物品，使得它们的体积之和不小于背包容量的前提下，尽可能的小。在满足这个前提下物品数要尽可能的少。
- 其实物品的数量我们不需要额外考虑，因为在满足 物品总体积 尽可能小的前提下，已经隐含了 物品数 尽可能的少。因为如果此时我们已经满足了物品总体积不小于背包容量，且物品总体积不可能更小，那么显然此时我们无法拿出任何物品。
- 已经知道了是01背包，可以很容易得到状态压缩下的转移方程：
f[j]=min(f[j],f[j-a[i]]);。f[j]：价值j最少需要f[j]枚硬币。a[i]：第i枚硬币的价值是a[i]。
- 直接套01背包模板会出错，因为01背包不需要考虑是否能填满，而是在不大于背包容量的前提下让物品总价值尽可能的大。我们可以在遍历背包容量时从更大的容量开始，那么从什么时候开始遍历呢？很容易想到的是从所有硬币总价值开始遍历，但是这样做会超时。事实上我们没有必要遍历全部的价值。
- 因为目标钱最多是10000，而每个硬币的最大价值是10000，所以极限情况是目标价值：10000，硬币：9999 9999 9999 9999 ，最多遍历到20000就够了。
- 最后我们需要从m（目标价值）开始遍历，最多到20000结束，寻找不小于m的价值中可以凑齐的最小价值。
- 如欲了解更多背包问题：背包问题模板 | ❤梧桐苑
01背包代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e2+50;
const int M=2e4+10;
typedef long long ll;
int a[N];
int f[M];//达到价值i最少要f[i]枚硬币
int main()
{
int t;
cin>>t;
while(t--)
{
int m,n;//目标钱 硬币数
cin>>m>>n;
for(int i=1;i<=n;++i) cin>>a[i];
memset(f,0x3f3f3f3f,sizeof f);
f[0]=0;//价值0不需要硬币
for(int i=1;i<=n;++i)
{
//从所有硬币总价值开始遍历会超时
//事实上我们没有必要遍历全部的价值。因为目标钱最多是10000，而每个硬币的最大价值是10000，
//所以极限情况是目标钱10000，硬币9999 9999 9999 9999 ，最多遍历到20000就够了
for(int j=M;j>=a[i];--j)
f[j]=min(f[j],f[j-a[i]]+1);
}
for(int i=m;i<=M;++i)
{
if(f[i]<=n)
{
cout<<i<<" "<<f[i]<<endl;
break;
}
}
}
//system("pause");
return 0;
}算法实验10：会场安排问题
题目： 会场安排问题
题意：
假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。（这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。） 对于给定的k个待安排的活动，计算使用最少会场的时间表。
输入格式
输入数据的第一行有1 个正整数k（k≤10000），表示有k个待安排的活动。接下来的k行中，每行有2个正整数，分别表示k个待安排的活动开始时间和结束时间。时间以0 点开始的分钟计。
输出格式
输出一个整数，表示最少会场数。
数据范围
1 ≤ k ≤ 10000
输入样例：
5
1 23
12 28
25 35
27 80
36 50输出样例：
3思路：
- 贪心 。这道题目是“活动安排”题目的变形。“活动安排”要求我们在一间会场中安排活动，求最多能安排多少不冲突的活动；而该题会场数量不限，要求所有活动都要安排到某一间会场中，求最后最少需要多少会场。
- 优先队列 。考虑将所有活动按开始时间排序，将最先开始的活动安排到第一间会场中，然后从第二件活动开始遍历，看已经安排了活动的会场中最后一件活动的结束时间是否小于当前活动，如果有就将当前活动加入到其中 任意 一间会场中。否则就新开一间会场，放入该活动。
- 为什么可以任意放到满足要求的会场中？因为我们是按活动开始排序的，如果当前活动的开始时间大于目前所有会场的结束时间，那么后面的活动也一定满足该条件，同时由于活动的结束时间是固定的，所以无论我们放到哪一间会场，结束时间都相同。
- 如何快速找到满足条件的会场？优先队列实现。优先队列会自动对放入的会场结束时间升序排序，所以如果队首元素不满足条件，那么后面的所有会场也一定不满足。同理如果至少有一间会场满足，那么队首元素也一定满足。
- 双指针算法 。比较牛的一种做法。本质上是一个模拟的过程，遍历所有活动看是否有空闲的会场：
- 如果有，将该活动安排到最早结束的会场。中。
- 如果没有就新开一个会场。
- 重点在于对开始时间的遍历，与优先队列核心思想是一致的
- 参考： 会场安排问题 | ❤梧桐苑
优先队列代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef pair<int, int> PII;
typedef long long ll;
int n;
PII p[N];//first开始时间 second结束时间
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> p[i].first >> p[i].second;
sort(p+1, p+n+1);
q.push(p[1].second);
for (int i = 2; i <= n; ++i)
{
if (q.top() <= p[i].first)
q.pop();
q.push(p[i].second);
}
cout<<q.size()<<endl;
system("pause");
return 0;
}双指针算法
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef pair<int, int> PII;
typedef long long ll;
int n;
int a[N],b[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) cin>>a[i]>>b[i];
sort(a,a+n);
sort(b,b+n);
int ans=0;
//本质上是一个模拟的过程，遍历所有活动的开始时间看是否有空闲的会场
for(int i=0,j=0;i<n;++i)
{
//b[j]表示当前所有已安排活动的会场中"最早"的结束时间
if(b[j]>a[i])ans++;
else ++j;
}
cout<<ans<<endl;
system("pause");
return 0;
}
