人工智能设计网站,青海餐饮网站建设,营销活动方案名称,暖通毕业设计代做网站题意理解#xff1a;给定一个区间#xff0c;我们需要把这个区间覆盖掉。问最少需要的区间数目。当然我们会给定 n 个区间选择。假设全选都不能覆盖就输出 − 1 -1 −1
思路分析#xff1a;我感觉应该是找区间的端点。假设区间的左端点是 s #xff0c;右端点是 t #…题意理解给定一个区间我们需要把这个区间覆盖掉。问最少需要的区间数目。当然我们会给定 n 个区间选择。假设全选都不能覆盖就输出 − 1 -1 −1
思路分析我感觉应该是找区间的端点。假设区间的左端点是 s 右端点是 t 我们枚举的区间的左端点尽可能靠近 s 右端点尽可能靠近 t 这样的贪心策略就可以使得选择的区间数目还需要检测区间内部是不是完整地被覆盖了。需要枚举的区间按照左端点排序。选择的是那个最靠近 s 的区间作为选择的第一个区间。更新的思路是找最大的左端点让这个左端点小于等于前面选择的区间的右端点这样才能保证被覆盖了。最后要判断区间的右端点要超过 t 这个点但是不能超过太多。但是我们贪心只能从一端开始贪心是不是要从左边往右边贪心一遍然后从右边往左边贪心一次然后取一个最小值呢。
看了一下题解好像和我的思路不是太像但是有一些相似之处毕竟同一题不过思路和实现之间隔着一个银河系感觉我没啥信心把这题写出来。
#includeiostream
#includealgorithmusing namespace std;const int N10000010;
int n;
int st,ed;
struct Range{int l,r;bool operator (const Range W)const{return lW.l;}
}range[N];int main(){scanf(%d%d,st,ed);scanf(%d,n);for(int i0;in;i){int l,r;scanf(%d%d,l,r);range[i]{l,r};}sort(range,rangen);int ans0;bool successfalse;for(int i0;in;i){int ji;int r-2e9;while(jnrange[j].lst){rmax(r,range[j].r);j;}if(rst){break;//表示不可能覆盖掉}ans;if(red){successtrue;break;}str;ij-1;//假设现在的 j 比较到某一位了找到了一个最大值然后我们更新了 st//我们需要枚举下一个区间但是这个时候已经不满足条件了所以需要返回前面那个//满足条件的区间应该是这个意思对的就是现在下一个区间的左端点没在 st 的左边//得更新 st }if(!success){ans-1;}printf(%d\n,ans);return 0;
}其他
故事的结局是否重要很多人以为的结局是这样一种场景杂志社的编辑告诉你还有三个月交稿多想多看写坏了没关系我们时间充裕重新再写好好写。
其实不是。
真正的结局是某个下午你午睡醒来在纸上潦草画了几笔房门忽然被敲响来人问你写到了哪不管上面写了什么你有多不甘心多想要修改这页就是结局。
世事无常人生不如意太多太多。
愿大家珍惜眼前人自己所爱之人所爱之事认真地过完这一生莫要后悔。
我家先生我喜欢他多年从高中开始直到现在。
感触颇深。
