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