社区讨论

我的代码为啥过不了呢,求回答!

P1047[NOIP 2005 普及组] 校门外的树参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lxzvwmlg
此快照首次捕获于
2024/06/29 16:52
2 年前
此快照最后确认于
2024/06/29 20:09
2 年前
查看原帖
用的是区间合并,如果看完回答十分感谢!
CPP
#include <bits/stdc++.h>
using namespace std;
// l表示马路的长度,n表示区域的段数,st,ed表开始结束
int l, n, st, ed;
typedef vector<pair<int, int>> arr;
arr segs;
int func(arr segs)
{
    arr temp;
    int ans;
    sort(segs.begin(), segs.end());
    int st = -1e9, ed = -1e9;
    for (auto seg : segs)
    {
        if (ed < seg.first)
        {
            if (ed != -1e9)
                temp.push_back({st, ed});
            st = seg.first;
            ed = seg.second;
        }
        else
            ed = max(ed, seg.second);
    }
    if (ed != -1e9)
        temp.push_back({st, ed});
    for (auto seg : temp)
    {
        ans += seg.second - seg.first + 1;
    }
    return ans;
}

int main()
{
    cin >> l >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> st >> ed;
        segs.push_back({st, ed});
    }
    int ans = l + 1 - func(segs);
    printf("%d", ans);
    return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...