一、区间问题
思想：
将每个区间按右端点按小到大排序
从前往后依次枚举每个区间，如果当前区间已经包含选择的点，则直接跳过，否则选择当前区间的右端点
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
struct Range
{
int l;
int r;
}range[N];
int n;
int ans = 1;//默认选一个点表示第一个区间
bool cmp(Range a,Range b)
{
return a.r < b.r;
}
int main()
{
cin>>n;
for(int i = 0;i < n;i++)
{
cin>>range[i].l>>range[i].r;
}
sort(range,range + n,cmp); //将区间按右端点从小到大排序
int last = range[0].r;
for(int i = 1;i < n;i++)
{
if(range[i].l > last) //由于右端点从小到大排序，若当前区间左端点大于上一区间右端点
//说明二者无交集，不可能用上一区间的点表示本区间，必须在本区间再找一个点
{
ans++;
last = range[i].r;
}
}
cout<<ans<<endl;
return 0;
}
908. 最大不相交区间数量
左端点排序做法
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
struct Range
{
int l;
int r;
}range[N];
int n,a,b;
int ans = 1;
bool cmp(Range a,Range b)
{
return a.l < b.l;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a>>b;
range[i] = {a,b};
}
sort(range,range+n,cmp);
int last = range[n-1].l;
for(int i = n-2;i>=0;i--)
{
if(range[i].r < last)
{
ans++;
last = range[i].l;
}
}
cout<<ans<<endl;
return 0;
}
906. 区间分组
给定 N 个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
输出最小组数。
输入格式
第一行包含整数 N，表示区间数。
接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示最小组数。
数据范围
1≤N≤105,
−109≤ai≤bi≤109
O(nlogn)
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 1e5+10;
struct Range
{
int l;
int r;
}range[N];
int n,a,b;
bool cmp(Range a,Range b)
{
return a.l < b.l;
}
int main()
{
cin>>n;
for(int i = 0;i < n;i++)
{
cin>>a>>b;
range[i] = {a,b};
}
sort(range,range + n,cmp);//按左端点从小到大对区间排序
priority_queue<int,vector<int>,greater<int>>heap; //定义小根堆
for(int i = 0;i < n;i++)
{
if(heap.empty() || range[i].l <= heap.top()) //组数为0 或者 当前区间左端点比最靠左的组右端点小
//说明不能放进组里，否则会冲突，因此必须新开一个组
{
heap.push(range[i].r);
}
else //不会发生冲突，可以放进最靠左的组，更新组的最大右端点
{
heap.pop();
heap.push(range[i].r);
}
}
cout<<heap.size()<<endl;//堆中元素个数就是组的数量
return 0;
}
112
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
struct Range
{
int l;
int r;
}range[N];
int a,b,n;
int st,ed;//线段的左右端点
bool cmp(Range a,Range b)
{
return a.l < b.l;
}
int main()
{
cin>>st>>ed;
cin>>n;
for(int i = 0;i < n;i++)
{
cin>>a>>b;
range[i] = {a,b};
}
sort(range,range+n,cmp); //将区间按左边界从小到大排序
int res = 0,r = -2e9;//选择的区间个数，当前选择区间的右边界
bool state = false;//当前选择的所有区间是否已全部包含线段
for(int i = 0;i < n;i++)
{
int j = i;
r = -2e9;
for(j = i;j < n && range[j].l <= st;j++) //找出左端点不大于当前线段且右端点最大的区间
{
r = max(r,range[j].r);
}
if(r < st) //选定区间右端点比线段的左区间还小，说明根本无法覆盖，直接跳出
{
res = -1;
break;
}
res++; //判断有覆盖的可能性后加入当前区间到选择中，选择区间总数加1
if(r >= ed) //若当前选定区间右端点大于线段右端点，说明成功覆盖
{
state = true;
break;
}
st = r;//将start更新成选定区间的右端点
i = j - 1;//for循环i也要加，故赋值j-1，主要用于优化算法
}
if(state == false) res = -1;
cout<<res<<endl;
return 0;
}
二、哈夫曼树
数据结构课程中学过了，在此不多赘述
148. 合并果子
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int n,sum,x;
priority_queue<int,vector<int>,greater<int>>heap;
int main()
{
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>x;
heap.push(x);
}
while(heap.size() > 1)
{
int a = heap.top();
heap.pop();
int b = heap.top();
heap.pop();
sum += a + b;
heap.push(a + b);
}
cout<<sum<<endl;
return 0;
}
三、排序不等式
913. 排队打水总时间 = t1 * (n-1) + t2 * (n-2) + …… + tn-1 * 1 + tn * 0
思路
按照从小到大的顺序，总时间最小
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N],n;
long long sum;
int main()
{
cin>>n;
for(int i = 1;i <= n;i++) cin>>a[i];
sort(a+1,a+n+1);
for(int i = 1;i <= n;i++)
{
sum += a[i] * (n-i);
}
cout<<sum<<endl;
return 0;
}
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N],n,sum;
int main()
{
cin>>n;
for(int i = 0;i<n;i++) cin>>a[i];
sort(a,a+n);
for(int i = 0;i < n;i++)
{
sum+= abs(a[i] - a[n/2]); //仓库取在中位数上，使得仓库在所有a[1]~a[n],a[2]~a[n-1]距离最小
}
cout<<sum<<endl;
return 0;
}
四、推公式
125. 耍杂技的牛
牛的重量和强壮度之和越大，越要放到下面
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 50005;
struct cow
{
int w;
int s;
bool operator<(const cow& t)
{
return w+s < t.w + t.s;
}
}cows[N];
int sum[N];
int n,w,s,danger = -0x3f3f3f3f;
int main()
{
cin>>n;
for(int i = 1;i <= n;i++)
{
cin>>w>>s;
cows[i] = {w,s};
}
sort(cows+1,cows+n+1);
for(int i = 1;i <= n;i++)
{
sum[i] = sum[i-1] + cows[i].w;
}
for(int i = 1;i <= n;i++)
{
danger = max(danger,sum[i-1] - cows[i].s);
}
cout<<danger<<endl;
return 0;
}
五、时空复杂度分析
一般ACM或者笔试题的时间限制是1秒或2秒。
在这种情况下，C++代码中的操作次数控制在 107∼108107∼108 为最佳。
下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：
n≤30n≤30, 指数级别, dfs+剪枝，状态压缩dp
n≤100n≤100 => O(n3)O(n3)，floyd，dp，高斯消元
n≤1000n≤1000 => O(n2)O(n2)，O(n2logn)O(n2logn)，dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
n≤10000n≤10000 => O(n∗n√)O(n∗n)，块状链表、分块、莫队
n≤100000n≤100000 => O(nlogn)O(nlogn) => 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
n≤1000000n≤1000000 => O(n)O(n), 以及常数较小的 O(nlogn)O(nlogn) 算法 => 单调队列、 hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 O(nlogn)O(nlogn) 的做法：sort、树状数组、heap、dijkstra、spfa
n≤10000000n≤10000000 => O(n)O(n)，双指针扫描、kmp、AC自动机、线性筛素数
n≤109n≤109 => O(n√)O(n)，判断质数
n≤1018n≤1018 => O(logn)O(logn)，最大公约数，快速幂，数位DP
n≤101000n≤101000 => O((logn)2)O((logn)2)，高精度加减乘除
n≤10100000n≤10100000 => O(logk×loglogk)，k表示位数O(logk×loglogk)，k表示位数，高精度加减、FFT/NTT