【基础练习】【贪心】codevs1214 线段覆盖题解

偏执的太偏执、 2022-08-07 09:41 210阅读 0赞

题目：已知数轴上0<N<10000条线段。每条线段按照端点Ai和Bi（Ai<>Bi,i=1..N）定义。端点坐标在（-999，999）内，坐标为整数。有些线段可能相交。编程实现删除最少数目的线段，使得余下的任意两条线段不相交。

codevs和洛谷数据范围不同 改一下常量maxn即可

思路是很简单的贪心

//codevs1214 线段覆盖 贪心
    //先排序，扫描一遍，每次保留右端点最小的线段，重叠的delete，画一张图即可证明
    #include<cstdio>
    #include<cstring>
    using namespace std;
    
    const int maxn=100+10;
    int l[maxn],r[maxn];
    bool st[maxn];
    
    int main(){
    	int n;
    	scanf("%d",&n);
    	for (int i=0;i<n;i++){
    		scanf("%d%d",&l[i],&r[i]);
    		if (l[i]>r[i]){
    			int temp=l[i];
    			l[i]=r[i];
    			r[i]=temp;
    		}
        }
        for (int i=0;i<n;i++){
        	for (int j=i+1;j<n;j++){
        		if (r[i]>r[j]){
        			int temp1=r[i];
        			int temp2=l[i];
        			r[i]=r[j];l[i]=l[j];
        			r[j]=temp1;l[j]=temp2;
    			}
    		}
    	}
    	memset(st,true,sizeof(st));
    	for (int i=0;i<n;i++){
    		if (st[i]){
    			for (int j=i+1;j<n;j++){
    				if (st[j]&&(l[j]<r[i])){
    					st[j]=false;
    				}
    			}
    		}
    	} 
    	int ans=0;
    	for (int i=0;i<n;i++) if (st[i]) ans++;
    	printf("%d",ans);
    	return 0;
    }

——自牧归荑，洵美且异；匪女之为美，美人之贻。

发表评论取消回复

表情：

评论列表（有 0 条评论，210人围观）

还没有评论，来说两句吧...

相关阅读

相关【基础练习】【差分】codevs1242 布局题解

题目描述 Description 当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。FJ有N（2<=N<=1000）头奶牛，编号从1到N，沿一条直线站着等候喂食。奶牛排在队伍

青旅半醒/ 2022年08月09日 17:40/ 0 赞/ 199 阅读

相关【基础练习】【二分图匹配】【匈牙利算法】codevs1022 覆盖题解

题目描述 Description 有一个N×M的单位方格中，其中有些方格是水塘，其他方格是陆地。如果要用1×2的矩阵区覆盖（覆盖过程不容许有任何部分重叠）这个陆地，那么最多可

清疚/ 2022年08月09日 15:52/ 0 赞/ 208 阅读

相关【基础练习】【贪心】codevs2612 最优分解方案题解

题目描述 Description 为了迎接圣诞，信息学兴趣小组的同学在辅导老师的带领下，举办了一个盛大的晚会，晚会的主要内容是做游戏。经过第一轮的游戏，不少同学将会获得圣诞特

约定不等于承诺〃/ 2022年08月09日 06:17/ 0 赞/ 251 阅读

相关【基础练习】【SPFA】codevs1557 热浪题解

题目描述 Description 德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生產富含奶油的乳製品。Farmer

﹏ヽ暗。殇╰゛Y/ 2022年08月09日 03:29/ 0 赞/ 18 阅读

相关【基础练习】【栈】codevs2058 括号匹配题解

这道题目就不多说了非常经典的栈练习左括号压栈，右括号比较布尔变量判断即可曾经写过一到类似的表达式求值博客上有可以参考这道题目的最后一个点非常坑不知道哪里

朱雀/ 2022年08月08日 06:57/ 0 赞/ 220 阅读

相关【基础练习】【贪心】codevs1214 线段覆盖题解

题目：已知数轴上0<N<10000条线段。每条线段按照端点Ai和Bi（Ai<>Bi,i=1..N）定义。端点坐标在（-999，999）内，坐标为整数。有些线段可能相交。编程实现

偏执的太偏执、/ 2022年08月07日 09:41/ 0 赞/ 211 阅读

相关【基础练习】【堆】codevs1063 合并果子题解

是的我受不了诸城一中的魔鬼DEVCPP了还有魔鬼codeblocks 每次编译都要把六个文件都点一遍删除可执行文件再重新编译= =命令行也各种问题受不了他直接

￡神魔★判官ぃ/ 2022年08月02日 15:53/ 0 赞/ 248 阅读

相关【基础练习】【线性DP】codevs3027 线段覆盖2题解

文章被盗还是很严重，加版权信息转载请注明出处 \[[ametake][]版权所有\][http://blog.csdn.net/ametake][ametake]欢迎来看看

﹏ヽ暗。殇╰゛Y/ 2022年08月02日 00:10/ 0 赞/ 216 阅读

相关【基础练习】【贪心】codevs1214 线段覆盖题解

文章被盗还是很严重，加版权信息转载请注明出处 \[[ametake][]版权所有\][http://blog.csdn.net/ametake][ametake]欢迎来看看

我就是我/ 2022年08月01日 15:53/ 0 赞/ 231 阅读

相关 wikioi1214-线段覆盖

线段覆盖题目描述 Description 给定x轴上的N（0<N<100）条线段，每个线段由它的二个端点a\_I和b\_I确定，I=1,2,……N.这些坐标都是区间（－9

刺骨的言语ヽ痛彻心扉/ 2022年07月26日 00:30/ 0 赞/ 179 阅读