首页 > 其他分享 >D - Intersecting Intervals

D - Intersecting Intervals

时间:2024-05-25 23:12:06浏览次数:18  
标签:NODE return struct int Intervals end Intersecting cout

D - Intersecting Intervals

 

思路

对于区间重合问题, 经典做法 对 left 进行排序, 然后进行统计计数。

写了一版TLE,反思有冗余计数问题。

计算每一个区间的覆盖数目, 不需要TLE版本逐个往后数,

只需要使用lower_bound找出第一个大于等于 ri + 1  的位置, 即可得到 与i区间 重合区间的数目。

 

 

Code (TLE)

https://atcoder.jp/contests/abc355/submissions/53886635

struct NODE{
    int l;
    int r;
};

int n;

vector<struct NODE> c;

bool cmp(struct NODE& a, struct NODE& b){
    if (a.l < b.l){
        return true;
    }
    
    return false;
}


int main()
{
    cin >> n;
    c.resize(n);

    for(int i=0; i<n; i++){
        cin >> c[i].l >> c[i].r;
    }

    sort(c.begin(), c.end(), cmp);

//    for(auto one: c){
//        cout << one.l <<endl;
//    }

    long long cnt = 0;

    for(int i=0; i<n; i++){
        struct NODE& cur = c[i];
        int curl = cur.l;
        int curr = cur.r;
        
        for(int j=i+1; j<n; j++){
            struct NODE& re = c[j]; // right elments
            
            int rel = re.l;
            int rer = re.r;
            
            if (rel > curr){
                break;
            }
            
            cnt++;
        }
    }
    
    cout << cnt << endl;

    return 0;
}

 

 

Code (PASS)

https://atcoder.jp/contests/abc355/submissions/53899306

struct NODE{
    int l;
    int r;
};

int n;

vector<struct NODE> c;

bool cmp(struct NODE& a, struct NODE& b){
    if (a.l < b.l){
        return true;
    }

    return false;
}


int main()
{
    cin >> n;
    c.resize(n);

    for(int i=0; i<n; i++){
        cin >> c[i].l >> c[i].r;
    }

    sort(c.begin(), c.end(), cmp);

//    for(auto one: c){
//        cout << one.l <<endl;
//    }

    long long cnt = 0;

    for(int i=0; i<n; i++){
        vector<struct NODE>::iterator it;
        it = lower_bound(c.begin(), c.end(), c[i].r+1, [](const struct NODE &a, const int &val) {
            return a.l < val;
        });
        
        if (it == c.end()){
//            cout << "to end" << endl;
            cnt += n-1 - i;
            continue;
        }
        
        int greatpos = it - c.begin();
        
        cnt += (greatpos - i - 1);
    }

    cout << cnt << endl;

    return 0;
}

 

标签:NODE,return,struct,int,Intervals,end,Intersecting,cout
From: https://www.cnblogs.com/lightsong/p/18213141

相关文章

  • CF1909C Heavy Intervals 题解
    一种似乎更快抽象的解法?题面正文看这道题,给定序列\(l,r,c\),要求重构\(l,r,c\)使得\(\sum_{i=1}^n(r_i-l_i)\timesc_i\)最小。首先可以想到的就是尽量让小的\(r_i-l_i\)乘上大的\(c_i\)。这样子看来\(c_i\)几乎不需要更多的处理,仅需从小到大(或从大到小)排个序。来......
  • 【Java编程】【算法面试题】【数组合并】以数组 intervals 表示若干个区间的集合,其中
    原始题目:以数组intervals表示若干个区间的集合,其中单个区间为intervals[i]=[starti,endi]。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。......
  • 题解 ARC175C【Jumping Through Intervals】
    先不考虑构造字典序最小的方案,只考虑求出最小的\(\sum\limits_{i=1}^{N-1}|A_{i+1}-A_i|\)。设定义域为\([L_i,R_i]\)的函数\(F_i(x)\)表示考虑后缀\([i,N]\),令\(A_i=x\)时上式最小的值。初值为\(F_N(x)=0,(x\in[L_N,R_N])\)。显然有转移方程:\[F_i(x)=\min\limits_{y......
  • Elastic intervals的使用
    在Elasticsearch中,intervals查询是用来做复杂的区间表达式匹配的,它可以基于分析过的文本字段执行一系列复杂的关系运算。intervals查询特别适合于那些需要对文本数据进行模式匹配,而不只是单一词汇匹配的情况。intervals语法GETyour_index/_search{"query":{"in......
  • CF1861E Non-Intersecting Subpermutations 题解
    简要题意一个长度为\(n\)的元素在\([1,k]\)的整数序列\(a\)的价值定义如下。初始\(i=1\),如果\(a_{i\simi+k-1}\)包含了\(1\simk\)的所有整数,则价值加\(1\),然后令\(i=i+k\)。如果没有包含\(1\simk\)的所有整数则\(i=i+1\),直到\(i\geqn-k+2\)时结束。......
  • C. Heavy Intervals
    C.HeavyIntervalsYouhave$n$intervals$[l_1,r_1],[l_2,r_2],\dots,[l_n,r_n]$,suchthat$l_i<r_i$foreach$i$,andalltheendpointsoftheintervalsaredistinct.The$i$-thintervalhasweight$c_i$perunitlength.Therefore,theweight......
  • [题解] AT_dp_w Intervals
    Intervals有\(m\)条形如\((l,r,a)\)的限制,表示如果\(s_{[l,r]}\)中有1就会有\(a\)的价值。你要求长度为\(n\)的01串的价值的最大值。\(n,m\le2\times10^5\)。将每个限制挂到右端点上,在右端点处计算贡献。然后我们就只关心最后一个1出现的位置了。......
  • 【刷题笔记】56. Merge Intervals
    题目Givenacollectionofintervals,mergealloverlappingintervals.Example1:Input:[[1,3],[2,6],[8,10],[15,18]]Output:[[1,6],[8,10],[15,18]]Explanation:Sinceintervals[1,3]and[2,6]overlaps,mergetheminto[1,6].Example2:Input:[[1,4],[4,5......
  • poj 1716 Integer Intervals (贪心)
    题意:给定n个连续的区间,求一个集合。其中,n个区间的每一个区间都至少包含两个这个集合的元素。求这个集合元素的最小值。 题解:1、先将所有区间按终点从小到大排序。2、我们先取第一个区间(排好序的区间)的两个值,因为要使得结果最优,我们肯定选择最接近终点的那两个值。假设一个为Selem,......
  • CF1034D Intervals of Intervals
    简要题意给定\(n\)个区间组成的序列,定义它的一个连续段的价值为这个段内所有区间的并覆盖的长度。求价值前\(k\)大的段的价值和。数据范围:\(1\len\le3\times10^5,1\lek\le\min\{\frac{n(n-1)}{2},10^9\}\)。题解考虑一个经典问题,\(q\)次询问求某个连续段的价值。......