#创作计划#阳坡湖集训笔记day1(补)
2025-07-23 19:34:49
发布于:浙江
题目:
在神秘的森林中,
N 只迷路的小动物分别躲在不同的区域中。每个区域可以用一个闭区间
[ai,bi](例如[1,5][1,5]表示闭区间包含 1 , 2 , 3 , 4 , 5 这 5 个点) 来表示,小动物们可能在这个区间的任何位置(包括端点)。
探险家昱栋需要选择尽可能少的食物投放点,确保每个区域内的小动物都能够吃到食物。
请你帮助昱栋计算,他最少需要在数轴上的哪些投放点投放食物,才能让所有的小动物吃饱!
这个题是一道结构体排序还有边界的判断,
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+9;
struct node{
int l,r;
}a[N];
bool cmp(node x,node y){
return x.r<y.r;
}
signed main(){
int n;
cin>>n;
for(int i = 1;i <= n;i++)cin>>a[i].l>>a[i].r;
sort(a+1,a+1+n,cmp);
int res=0,end=-2e9;
for(int i =1;i <= n;i++){
if(a[i].l>end){
end=a[i].r;
res++;
}
}
cout<<res;
return 0;
}
代码最重要的部分是判断边界的地方,如果当前的左边界在上一个的右边界之外,那么还需放一个投喂点,同时,end也变为当前的右边界
这里空空如也
有帮助,赞一个