贪心——区间问题
一、区间选点问题
1、区间问题
1、思路
给定N个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。输出选择的点的最小数量。
将每个区间按照右端点从小到大排序，然后从前往后依次枚举每个区间。
如果下一个区间和当前区间没有交点，就新开一个，点+1
如果有交点，直接过。
当一个问题是单峰的，可以用贪心，因为贪心选的是当前的最优解，
如果是多峰，可能有问题，即局部最优解不一定是全局最优解
2、代码模板：
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
struct Range{ //结构体存区间，左右边界
int l,r;
bool operator< (const Range &W)const//重载运算符<
{
return r<W.r;
}
}range[N];
int main()
{
int n;
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,ed=-2e9;//初始化左右边界
for(int i=0;i<n;i++)//枚举n个区间
{
if(range[i].l>ed)//如果下一区间的左边界大于上一个区间的右边界，即两区间不相交
{
res++; //点+1
ed=range[i].r;//右边界更新为新区间的右边界
}
}
printf("%d",res);
return 0;
}
2、最小不相交数量.908
1、思路
与第一题思路相同
按照每个区间的右边界从小到大排序
然后依次枚举，如果下一区间的左边界大于上一区间的右边界，即不相交，区间数+1
相交就更新右端点，区间数不变
2、代码模板：
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
struct Range{ //结构体存区间，左右边界
int l,r;
bool operator < (const Range &W)const//重载运算符<
{
return r<W.r;
}
}range[N];
int main()
{
int n;
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(range[i].l>ed)//如果下一区间的左边界大于上一个区间的右边界，即两区间不相交
{
res++;
ed=range[i].r;//右边界更新为新区间的右边界
}
}
printf("%d",res);
return 0;
}
3、区间分组
1、思路
把所有区间按照左边界从小到大排序，
从前往后处理每个区间
判断能否将新区间放到某个现有的组中，
如果可以，就放到原有的组中，并且更新右端点，存在多个的话就随便进一个
如果不可以，就开一个新组放进去。
2、代码模板：
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+10;
struct Range //结构体存区间，左右边界
{
int l,r;
bool operator < (const Range &W)const //重载运算符<
{
return l<W.l;
}
}range[N];
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)//输入每个区间的左右端点
scanf("%d %d",&range[i].l,&range[i].r);
sort(range,range+n);//按照每个区间的左边界从小到大排序
priority_queue<int,vector<int>,greater<int>> heap;//小根堆，从小到大
for(int i=0;i<n;i++)
{
Range x=range[i];
if(heap.empty()||heap.top()>=x.l)//如果队列为空或者两个区间有交点
heap.push(x.r); //新建一个分组
else //没有交点可以合成一个组
{
int t=heap.top();//暂存队头
heap.pop(); //删除队头
heap.push(x.r); //把新区间加入这一组，同时更新这一组的右端点，入队
}
}
printf("%d",heap.size());//看队列的元素有几个
return 0;
}
4、区间覆盖
1、思路
给定N个闭区间 [ai,bi]以及一个线段区间 [s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖，输出最少区间数。
将所有的区间按照左端点从小到大排序，设目标区间左端点为st，右端点为ed
第一步在所有包含st的区间中，选择右边界最大的区间r
然后将st更新为r，再在所有包含st区间中选择右边界最大的区间。
更新到大于等于ed时结束。
如果更新不到，就不能覆盖。
2、代码模板：
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
struct Range{ //自定义结构体存每一个区间的左右边界
int l,r;
bool operator< (const Range W)const //重载运算符<
{
return l<W.l;
}
}range[N];
int main()
{
int st,ed,n;
scanf("%d %d",&st,&ed);
scanf("%d",&n);
for(int i=0;i<n;i++)//读入n个区间
scanf("%d %d",&range[i].l,&range[i].r);
int res=0;
bool succes=false;
sort(range,range+n);//按照每个区间左边界从小到大排序
for(int i=0;i<n;i++)
{
int j=i,r=-2e9;//初始右端点为负无穷
while(j<n&&range[j].l<=st)//当下一个新区间的左边界小于st时，即st可能在区间里
{
r=max(r,range[j].r);//找出最大的右端点
j++;
}
if(r<st)//当所有可能包含st的区间的右边界的最大值都没超过st
{
res=-1;//区间不能覆盖
break;
}
res++;//r>=st时，区间数加一
if(r>=ed)//如果最大的右边界大于等于ed时，就是覆盖完成了
{
succes=true;
break;
}
st=r;//还有没覆盖的，就更新st继续
i=j-1;//更新i
}
if(!succes)//如果不能覆盖
res=-1;
printf("%d",res);
return 0;
}
二、Huffman树问题
1、思路
每一次合并，达达可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和，设计出合并的次序方案，使达达耗费的体力最少，并输出这个最小的体力耗费值。
这个问题用树可以很直观的看出，深度越深的点，被加的次数就越多。
所以取最小的两个点，最优情况一定是深度最深，而且可以互为兄弟。
2、代码模板：
#include<iostream>
#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)//当有1个以上堆果子时
{
int a=heap.top();
heap.pop();
int b=heap.top();
heap.pop();
res+=a+b;//记录最小的两堆果子的和
heap.push(a+b);//将最小的两堆果子和入队
}
printf("%d",res);
return 0;
}
三、不等式问题
1、排序不等式
1、思路
有n个人排队到1个水龙头处打水，第i个人装满水桶所需的时间是ti，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？
每一个位置打水时，会让他之后的所有人等待他打水的时间
显然，越靠前的人要是打水时间越短，所有人的等待时间之和就越小
所有把所有人打水要的时间从小到大排序，然后依次打水，总时间最少。
2、代码模板：
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
typedef long long ll;
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+=a[i]*(n-i-1);
printf("%lld",res);
return 0;
}
2、绝对值不等式
1、思路
在一条数轴上有N家商店，它们的坐标分别为A1∼AN。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
当前的距离和为：
我们对它进行分组，首尾分为一组
对于每一组我们可以保证xn在x1右边
所以，我们需要让仓库x尽量在更多组的中间，即中位数，
对于奇数个商店，就在最中间
对于偶数个商店，就在中间两个商店之间的任意一点。
2、代码模板：
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,a[N];
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);//从小到大排序
int res=0;
for(int i=0;i<n;i++)
res+=abs(a[i]-a[n/2]);//依次加上点到中间距离的位置
printf("%d",res);
return 0;
}
四、推公式
1、思路
这N头奶牛中的每一头都有着自己的重量wi以及自己的强壮程度si。风险值为一头牛它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。
方法：按照wi+si的和从小到大排，一定最小，
不让体重大的在上方，也不让可以抗很多的在上方。
2、代码模板：
#include<iostream>
#include<algorithm>
using namespace std;
const int N=5e4+10;
typedef pair<int,int> PII;//重量+强壮程度,强壮程度
int n;
PII cow[N];
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int x,y;
scanf("%d %d",&x,&y);
cow[i].first=x+y;
cow[i].second=y;
}
sort(cow,cow+n);//按照和排序
int res=-2e9,sum=0;//初始化最大值为负无穷，第i头牛上方牛的体重和sum=0
for(int i=0;i<n;i++)
{
int x=cow[i].first-cow[i].second;//x为第i头牛的体重
res=max(res,sum-cow[i].second);//算最大的危险程度
sum+=x;//加上体重
}
printf("%d",res);
return 0;
}
查看10道真题和解析
