一、区间选点（区间问题）
#include <iostream>
#include <algorithm>using namespace std;const int N = 100010;int n;
struct Range
{int l, r;bool operator< (const Range &W)const{return r < W.r;}
}range[N];int main()
{scanf("%d", &n);for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);sort(range, range + n);int res = 0, ed = -2e9;for (int i = 0; i < n; i ++ )if (ed < range[i].l){res ++ ;ed = range[i].r;}printf("%d\n", res);return 0;
}
二、最大不相交区间数量（区间问题）
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100010;
//保存区间
vector<vector<int>> a(N,vector<int>(2,0));
int n;int main()
{cin >> n;//读入区间for(int i = 0; i< n; i++){int l, r;cin >> l >> r;a[i][0] = l;a[i][1] = r;}// 按右端点排序sort(a.begin(), a.begin() + n, [](vector<int> &a, vector<int> &b){return a[1] < b[1];});// res 保存答案，end 最后一个选中区间的右端点int res = 0, end = -1e9 - 10;// 遍历区间for(int i = 0; i < n; i++){// 如果当前当前区间和最后一个选中区间有重合，则跳过if(end >= a[i][0] && end <= a[i][1]) continue;else{// 选中区间数量+1, 更右端点res++;end = a[i][1];}}cout << res;return 0;
}三、区间分组（区间问题）
#include <iostream>
#include <algorithm>using namespace std;const int N = 100100;int n;
int b[2 * N], idx;int main()
{scanf ("%d", &n);for(int i = 0; i < n; i ++){int l, r;scanf("%d %d", &l, &r);b[idx ++] = l * 2;//标记左端点为偶数。b[idx ++] = r * 2 + 1;// 标记右端点为奇数。}sort(b, b + idx);int res = 1, t = 0;for(int i = 0; i < idx; i ++){if(b[i] % 2 == 0) t ++;else t --;res = max(res, t);}printf ("%d\n", res);return 0;
}四、区间覆盖（区间问题）
#include <iostream>
#include <algorithm>using namespace std;const int N = 100010;int n;
struct Range
{int l, r;bool operator< (const Range &W)const{return l < W.l;}
}range[N];int main()
{int st, ed;scanf("%d%d", &st, &ed);scanf("%d", &n);for (int i = 0; i < n; i ++ ){int l, r;scanf("%d%d", &l, &r);range[i] = {l, r};}sort(range, range + n);int res = 0;bool success = false;for (int i = 0; i < n; i ++ ){int j = i, r = -2e9;while (j < n && range[j].l <= st){r = max(r, range[j].r);j ++ ;}if (r < st){res = -1;break;}res ++ ;if (r >= ed){success = true;break;}st = r;i = j - 1; }if (!success) res = -1;printf("%d\n", res);return 0;
}五、合并果子（Huffman树）
#include <iostream>
#include <algorithm>
#include <queue>using namespace std;int main()
{int n;scanf("%d", &n);priority_queue<int, vector<int>, greater<int>> heap;while (n -- ){int x;scanf("%d", &x);heap.push(x);}int res = 0;while (heap.size() > 1){int a = heap.top(); heap.pop();int b = heap.top(); heap.pop();res += a + b;heap.push(a + b);}printf("%d\n", res);return 0;
}
六、排队打水（排序不等式）
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 100010;
typedef long long LL;int n;
int a[N];int main()
{cin>>n;for (int i = 0; i < n; i ++ )cin>>a[i];sort(a, a+n);LL res = 0, t=0;for (int i = 0; i < n; i ++ ){res += t;t += a[i];}cout<<res<<endl;return 0;
}七、货仓选址（绝对值不等式）
八、耍杂技的牛（推公式）
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 5e4 + 5;
PII a[N];
int main()
{int n;cin >> n;for(int i = 0; i < n; i ++ ){int x, y;scanf("%d %d", &x, &y);a[i].first = x + y;a[i].second = y;}sort(a, a + n);ll res = -1e18, sum = 0;for(int i = 0; i < n; i ++ ){sum -= a[i].second;res = max(res, sum);sum += a[i].first;}cout << res << endl;return 0;
}