为什么只能ac2个点？
原题链接：65.校门外的树
2025-07-06 10:02:18
发布于：广东
19阅读
0回复
0点赞
不知道自己给的样例都能过
不知道为什么
为什么
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<unordered_map>
#define ll long long
#define si short int
#define pi 3.1415926
using namespace std;
const int N=3e5+9;
const ll INF=0xffffff;
struct node{
ll l,r;
bool allDel;
};
ll n,m,l,r,ans;
ll delT;
ll delL,delR,delM;
vector<node> chunk;
void set(ll dl,ll dr,ll dm) {
delL=dl;
delR=dr;
delM+=dm;//因为可能同时完全覆盖多个
if(delL+delR+delM>=delT) {
delL=0;
delR=0;
delM=delT;
}
}
int main()
{
cin>>n>>m;
ans=n+1;
while(m--) {
cin>>l>>r;
l=max(1ll*0,l);
r=min(n,r);
delT=r-l+1;
delL=0,delR=0,delM=0;
for(ll i=0;i<chunk.size();i++) {
if(!chunk[i].allDel) {
ll lastL=chunk[i].l,lastR=chunk[i].r;
if(l<=lastL && r>=lastR) {//覆盖原有结构 （可能多个）
set(0,0,lastR-lastL+1);
chunk[i].l=l,chunk[i].r=r;
}
else if(l>=lastL && r<=lastR) {//完全重叠
set(0,0,delT);
chunk[i].allDel=1;
}
else if(l<lastL && r<=lastR && r>lastL) {//右侧重叠
set(0,r-lastL+1,0);
chunk[i].l=l;
}
else if(l>=lastL && r>lastR && l<lastR) {//左侧重叠
set(0,lastR-l+1,0);
chunk[i].r=r;
}
}
}
ll cnt=delL+delR+delM;
if(cnt==0) chunk.push_back({l,r,0}); //没有任何重叠
delT-=cnt;
ans-=delT;
}
cout<<ans;
}
全部评论 2
#include<iostream> #include<vector> #include<algorithm> using namespace std; typedef long long ll; const int N = 3e5 + 9; // 存储已处理的有效区间（无重叠、按左边界排序） struct Interval { ll l, r; Interval(ll _l, ll _r) : l(_l), r(_r) {} }; vector<Interval> intervals; int main() { ll n, m; cin >> n >> m; ll total = n + 1; // 总树木数：0~n共n+1个点 ll ans = total; // 初始剩余树木数 = 总树木数 while (m--) { ll l, r; cin >> l >> r; // 确保区间在[0, n]内（题目中树的范围是0~n） l = max(ll(0), l); r = min(n, r); ll new_l = l; // 新区间的有效左边界（初始为输入l） ll new_r = r; // 新区间的有效右边界（初始为输入r） ll add = 0; // 本次新区间的有效移除长度（未被旧区间覆盖的部分） // 遍历所有已有的旧区间，处理重叠 for (auto& old : intervals) { // 仅处理“新区间与旧区间有重叠”的情况 if (new_l <= old.r && new_r >= old.l) { // 计算重叠部分的“有效新增长度”：旧区间覆盖了新区间的[overlap_l, overlap_r] ll overlap_l = max(new_l, old.l); ll overlap_r = min(new_r, old.r); add += (overlap_r - overlap_l + 1); // 累加重叠长度（即已被覆盖的部分） // 更新新区间的有效范围：排除已重叠的部分 if (overlap_l == new_l && overlap_r == new_r) { // 新区间完全被旧区间覆盖，后续无需处理 new_l = new_r + 1; break; } else if (overlap_l == new_l) { // 新区间左侧被覆盖，有效左边界更新为重叠右边界+1 new_l = overlap_r + 1; } else if (overlap_r == new_r) { // 新区间右侧被覆盖，有效右边界更新为重叠左边界-1 new_r = overlap_l - 1; } } } // 处理新区间中“未被任何旧区间覆盖”的部分 if (new_l <= new_r) { add += (new_r - new_l + 1); // 累加未重叠的有效移除长度 intervals.emplace_back(new_l, new_r); // 将新的有效区间加入列表 } // 从剩余树木数中减去本次有效移除长度 ans -= add; } cout << ans << endl; return 0; }1周前 来自 广东
0
有帮助，赞一个