题解 第二章暴力求解| #剩下的树#

剩下的树

http://www.nowcoder.com/practice/f5787c69f5cf41499ba4706bc93700a2

思路如下

创建一个结构体数组,每一个结构体中都存有区间的左右值

在取数组的时候对其进行遍历

使每一个新来的区间结构体,都将之前的所有有交集的区间给吸收

而将被吸收的区间置空

随后遍历一次该结构体数组

即可得待减去的个数

从而易知,剩下多少

#include <bits/stdc++.h>
using namespace std;

typedef struct interval
{
        int leftSide, rightSide;
} interval;

int main()
{
        int L = 0, repeatTimes = 0;
        cin >> L >> repeatTimes;
        interval inter[repeatTimes];
        for (int i = 0; i < repeatTimes; i++)
        {
                cin >> inter[i].leftSide >> inter[i].rightSide;
                for (int j = 0; j < i; j++)
                {
                        if ((inter[i].leftSide <= inter[j].rightSide && inter[i].leftSide >= inter[j].leftSide) ||
                            (inter[i].rightSide <= inter[j].rightSide && inter[i].rightSide >= inter[j].leftSide)||
                           (inter[j].leftSide <= inter[i].rightSide && inter[j].leftSide >= inter[i].leftSide) ||
                            (inter[j].rightSide <= inter[i].rightSide && inter[j].rightSide >= inter[i].leftSide))
                        {
                                inter[i].leftSide = min(inter[i].leftSide, inter[j].leftSide);
                                inter[i].rightSide = max(inter[i].rightSide, inter[j].rightSide);
                                inter[j].leftSide = 0;
                                inter[j].rightSide = -1;
                        }
                }
        }
        int minus = 0;
        for (int i = 0; i < repeatTimes; i++)
        {
                minus += inter[i].rightSide - inter[i].leftSide + 1;
        }
        cout << L + 1 - minus << endl;
        return 0;
}
王道机试指南刷题 文章被收录于专栏

计划刷完这本书

全部评论

相关推荐

07-07 11:33
江南大学 Java
已经在暑假实习了&nbsp;,没有明确说有hc,纠结实习到八月份会不会有点影响秋招毕竟感觉今年好多提前批
程序员小白条:92的话准备提前批,其他没必要,没面试机会的,而且你要准备充分,尤其八股和算法题
点赞 评论 收藏
分享
06-26 17:24
已编辑
宁波大学 golang
迷失西雅图:别给,纯kpi,别问我为什么知道
点赞 评论 收藏
分享
05-26 22:25
门头沟学院 Java
Java小肖:不会是想叫你过去把你打一顿吧,哈哈哈
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务