区间问题
区间选点
给定 N N N个闭区间 [ a i , b i ] [ai,bi] [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
输入格式
第一行包含整数N，表示区间数。
接下来 N N N行，每行包含两个整数 a i , b i ai,bi ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示所需的点的最小数量。
数据范围
1 ≤ N ≤ 1 0 5 1 \leq N \leq 10^{5} 1≤N≤105
− 1 0 9 ≤ a i ≤ b i ≤ 1 0 9 -10^{9} \leq a_{i} \leq b_{i} \leq 10^{9} −109≤ai≤bi≤109
思路
①将每个区间按右端点从小到大排序
②从前往后依次枚举每个区间
如果当前区间中已经包含点，则直接pass
否则，选择当前区间的右端点
证明上述方法是可行的：
c n t cnt cnt为所有可行解 a n s ans ans为可行解里的最小值 ∴ \therefore ∴ a n s < = c n t ans <= cnt ans<=cnt
c n t cnt cnt个互不相交的区间 至少要有 c n t cnt cnt个点 ∴ \therefore ∴ a n s > = c n t ans >= cnt ans>=cnt
∴ \therefore ∴ a n s = c n t ans = cnt ans=cnt
选最少的点 就要让一个点覆盖越多的区间 取右端点的话 就有更大的机会与后面的区间重合
#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<algorithm>
#include<vector>
#include<utility>
#include<deque>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) {
return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) {
return x & -x; }
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 100010;
struct Range {
int l, r;
}range[N];
bool cmp(struct Range a, struct Range b) {
return a.r < b.r;
}
int main() {
int n;cin >> n;
for (int i = 0; i <= n;++i) {
int l, r;
scanf("%d%d", &l, &r);
range[i] = {
l,r };
}
sort(range, range + n, cmp);
int res = 0, ed = -2e9;
for (int i = 0;i < n;++i) {
if (range[i].l > ed) {
res++;
ed = range[i].r;
}
}
cout << res << endl;
return 0;
}
最大不相交区间数量
给定 N N N个闭区间 [ a i , b i ] [ai,bi] [ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。
输出可选取区间的最大数量。
输入格式
第一行包含整数N，表示区间数。
接下来 N N N行，每行包含两个整数 a i , b i ai,bi ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示可选取区间的最大数量。
数据范围
1 ≤ N ≤ 1 0 5 1 \leq N \leq 10^{5} 1≤N≤105
− 1 0 9 ≤ a i ≤ b i ≤ 1 0 9 -10^{9} \leq a_{i} \leq b_{i} \leq 10^{9} −109≤ai≤bi≤109
思路
①将每个区间按右端点从小到大排序
②从前往后依次枚举每个区间
如果当前区间中已经包含点，则直接pass
否则，选择当前区间的右端点
类似排节目 一个节目越早结束 一场晚会就越能表演更多的节目
区间分组
给定 N N N个闭区间 [ a i , b i ] [ai,bi] [ai,bi],请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
输出最小组数。
输入格式
第一行包含整数 N N N，表示区间数。
接下来N行，每行包含两个整数 a i , b i ai,bi ai,bi,表示一个区间的两个端点。
输出格式
输出一个整数，表示最小组数。
数据范围
1 ≤ N ≤ 1 0 5 1 \leq N \leq 10^{5} 1≤N≤105
− 1 0 9 ≤ a i ≤ b i ≤ 1 0 9 -10^{9} \leq a_{i} \leq b_{i} \leq 10^{9} −109≤ai≤bi≤109
思路
①将所有区间按左端点从小到大排序
②从前往后处理每个区间
判断是否能将其放到现有的某个组中 l [ i ] > M a x r l[i] > Max_r l[i]>Maxr
1.如果不存在这样的组，则开新组，然后再将其放进去
2.如果存在这样的组，将其放进去，并更新当前组的Max_r
a n s ans ans为最优解 c n t cnt cnt为可行解 ∴ \therefore ∴ a n s < = c n t ans <= cnt ans<=cnt
而可行解的每个分组里至少有一个区间 可能有多个区间 ∴ \therefore ∴ a n s > = c n t ans >= cnt ans>=cnt
∴ \therefore ∴ a n s = = c n t ans == cnt ans==cnt
P S PS PS:按照左端点从小到大排序 当前区间的左端点 ≥ \geq ≥上一个区间的左端点 如果其左端点 ≤ \leq ≤上一区间右端点 则一定有交点 不能放在一组
#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<algorithm>
#include<vector>
#include<utility>
#include<deque>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) {
return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) {
return x & -x; }
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 100010;
int n;
struct Range {
int l, r;
}range[N];
bool cmp(struct Range a, struct Range b) {
return a.l < b.l;
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i) {
scanf("%d%d", &range[i].l, &range[i].r);
}
sort(range, range + n, cmp);
priority_queue<int, vector<int>, greater<int> >heap;
for (int i = 0;i < n; ++i) {
auto r = range[i];
if (heap.empty() || heap.top() >= r.l)heap.push(r.r);
else {
heap.pop();
heap.push(r.r);
}
}
cout << heap.size() << endl;
return 0;
}
区间覆盖
给定 N N N个闭区间 [ a i , b i ] [ai,bi] [ai,bi]以及一个线段区间 [ s , t ] [s,t] [s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。
输出最少区间数，如果无法完全覆盖则输出 − 1 -1 −1。
输入格式
第一行包含两个整数 s s s和 t t t，表示给定线段区间的两个端点。
第二行包含整数 N N N，表示给定区间数。
接下来N行，每行包含两个整数 a i , b i ai,bi ai,bi,表示一个区间的两个端点。
输出格式
输出一个整数，表示所需最少区间数。
如果无解，则输出-1。
数据范围
1 ≤ N ≤ 1 0 5 1 \leq N \leq 10^{5} 1≤N≤105
− 1 0 9 ≤ a i ≤ b i ≤ 1 0 9 -10^{9} \leq a_{i} \leq b_{i} \leq 10^{9} −109≤ai≤bi≤109
− 1 0 9 ≤ s ≤ t ≤ 1 0 9 -10^{9} \leq s \leq t \leq 10^{9} −109≤s≤t≤109
思路
①将所有区间按左端点从小到大排序
②从前往后依次枚举每个区间，在所有能覆盖 s t a r t start start的区间中，选择右端点最大的区间
选完之后将 s t a r t start start更新成右端点的最大值 依次选择区间并更新 s t a r t start start如果最后一次更新的 s t a r t < e n d start < end start<end 无解
#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<algorithm>
#include<vector>
#include<utility>
#include<deque>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) {
return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) {
return x & -x; }
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 100010;
int n;
int main() {
scanf("%d", &n);
priority_queue<int, vector<int>, greater<int>>p;
for (int i = 0;i < n;++i) {
int x;scanf("%d", &x);
p.push(x);
}
LL res = 0;
while (!p.empty()) {
if (p.size() != 1) {
int a = p.top();
p.pop();
int b = p.top();
p.pop();
res += (LL)a + b;
p.push(a + b);
}
else {
p.pop();
}
}
cout << res << endl;
return 0;
}
排序不等式
排队打水
有 n n n 个人排队到 1 1 1 个水龙头处打水，第 i i i 个人装满水桶所需的时间是 t i t_{i} ti，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？
输入格式
第一行包含整数 n n n。
第二行包含 n n n 个整数，其中第 i i i 个整数表示第 i i i 个人装满水桶所花费的时间 t i t_{i} ti
输出格式
输出一个整数，表示最小的等待时间之和。
数据范围
1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^{5} 1≤n≤105
1 ≤ t i ≤ 1 0 4 1 \leq t_{i} \leq 10^{4} 1≤ti≤104
思路
将时间按照从小到大的顺序排队，总时间最小
证明:反证法
假设 t i > t i + 1 t_{i} > t_{i+1} ti>ti+1
有 t i ∗ ( n − i ) + t i + 1 ∗ ( n − i − 1 ) t_{i}*(n-i) + t_{i+1}*(n-i-1) ti∗(n−i)+ti+1∗(n−i−1)①
交换 t i t_{i} ti和 t i + 1 t_{i+1} ti+1 有 t i + 1 ∗ ( n − i ) + t i ∗ ( n − i − 1 ) t_{i+1}*(n-i)+t_{i}*(n-i-1) ti+1∗(n−i)+ti∗(n−i−1)②
①-②得 t i − t i + 1 t_{i} - t_{i+1} ti−ti+1 而 t i > t i + 1 t_{i} > t_{i+1} ti>ti+1 ∴ \therefore ∴交换后总时间变小
若想使总时间最小 则 t i t_{i} ti应该从小到大排序 即 t i < t i + 1 t_{i}<t_{i+1} ti<ti+1
#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<algorithm>
#include<vector>
#include<utility>
#include<deque>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) {
return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) {
return x & -x; }
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 100010;
int a[N], n;
int main(){
scanf("%d", &n);
for (int i = 0; i < n;++i) {
scanf("%d", &a[i]);
}
sort(a, a + n);
LL res = 0;
for (int i = 0; i < n;++i)res += a[i] * (n - i - 1);
cout << res << endl;
return 0;
}
绝对值不等式
货仓选址
在一条数轴上有 N N N 家商店，它们的坐标分别为 A i − A N A_{i}-A_{N} Ai−AN。
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
输入格式
第一行输入整数 N N N.
第二行 N N N个整数 A i − A N A_{i}-A_{N} Ai−AN。
输出格式
输出一个整数，表示距离之和的最小值。
数据范围
1 ≤ N ≤ 100000 1 \leq N \leq 100000 1≤N≤100000
思路
对坐标进行排序 取每个点到中间点的距离
#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<algorithm>
#include<vector>
#include<utility>
#include<deque>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) {
return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) {
return x & -x; }
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 100010;
int n, a[N];
int main(){
scanf("%d", &n);
for (int i = 0; i < n;++i)scanf("%d", &a[i]);
sort(a, a + n);
LL res = 0;
for (int i = 0; i < n;++i)res += abs(a[i] - a[n / 2]);
printf("%lld\n", res);
return 0;
}
推公式
耍杂技的牛
农民约翰的N头奶牛（编号为 1.. N 1..N 1..N）计划逃跑并加入马戏团，为此它们决定练习表演杂技。
奶牛们不是非常有创意，只提出了一个杂技表演：
叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。
奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。
这N头奶牛中的每一头都有着自己的重量 w i w_{i} wi以及自己的强壮程度 s i s_{i} si
一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。
您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。
输入格式
第一行输入整数N，表示奶牛数量。
接下来N行，每行输入两个整数，表示牛的重量和强壮程度，第i行表示第i头牛的重量 w i w_{i} wi以及它的强壮程度 s i s_{i} si
输出格式
输出一个整数，表示最大风险值的最小可能值。
思路
按照 s [ i ] + w [ i ] s[i] + w[i] s[i]+w[i]从小到大排序 求最大值
设按照上述规则求得的答案为可行解 c n t cnt cnt 最优解为 a n s ans ans
∴ \therefore ∴ a n s ≤ c n t ans \leq cnt ans≤cnt
反证法:假设 s i + w i > s i + 1 + w i + 1 s_{i} + w_{i} > s_{i+1}+w_{i+1} si+wi>si+1+wi+1
第 i i i层 第 i + 1 i+1 i+1层
交换前: w 1 + w 2 + ⋯ + w i − 1 − s i w_{1} + w_{2} + \dots+w_{i-1} - s_{i} w1+w2+⋯+wi−1−si w 1 + w 2 + ⋯ + w i − s i + 1 w_{1} + w_{2} + \dots +w_{i} - s_{i+1} w1+w2+⋯+wi−si+1
交换后： w 1 + w 2 + ⋯ + w i − 1 − s i + 1 w_{1} + w_{2} + \dots+w_{i-1} - s_{i + 1} w1+w2+⋯+wi−1−si+1 w 1 + w 2 + ⋯ + w i − 1 + w i + 1 − s i w_{1} + w_{2} + \dots+w_{i - 1} + w_{i+1} - s_{i} w1+w2+⋯+wi−1+wi+1−si
化简：交换前： − s i - s_{i} −si w i − s i + 1 w_{i} - s_{i + 1} wi−si+1
交换后： − s i + 1 -s_{i+1} −si+1 w i + 1 − s i w_{i + 1} - s_{i} wi+1−si
同时加上 s i + s i + 1 s_{i} + s_{i + 1} si+si+1
交换前： s i + 1 s_{i + 1} si+1 w i + s i w_{i} + s_{i} wi+si
交换后： s i s_{i} si w i + 1 + s i + 1 w_{i + 1} + s_{i + 1} wi+1+si+1
∵ \because ∵ s i < w i + s i s_{i} < w_{i} + s_{i} si<wi+si & \And &已知 w i + 1 + s i + 1 < w i + w i w_{i + 1} + s_{i + 1} < w_{i} + w_{i} wi+1+si+1<wi+wi
∴ \therefore ∴ m a x ( s i , w i + 1 + s i + 1 ) ≤ w i + s i max(s_{i},w_{i + 1} + s_{i + 1}) \leq w_{i} + s_{i} max(si,wi+1+si+1)≤wi+si
∴ m a x ( s i , w i + 1 + s i + 1 ) ≤ m a x ( w i + s i , s i + 1 ) \therefore max(s_{i},w_{i + 1} + s_{i + 1}) \leq max(w_{i} + s_{i},s_{i + 1}) ∴max(si,wi+1+si+1)≤max(wi+si,si+1)
∴ \therefore ∴ 交换后最大风险值的最小可能指变小了 说明原思路正确
#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<algorithm>
#include<vector>
#include<utility>
#include<deque>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) {
return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) {
return x & -x; }
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 50010;
int n;
struct Node {
int s, w;
}node[N];
bool cmp(Node a, Node b) {
return a.s + a.w < b.s + b.w;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n;++i) {
scanf("%d%d", &node[i].w, &node[i].s);
}
sort(node, node + n, cmp);
LL sum = 0, res = -2e9;
for (int i = 0; i < n;++i) {
res = max(res, sum - node[i].s);
sum += node[i].w;
}
printf("%lld\n", res);
return 0;
}
京公网安备 11010502036488号