题解没看懂,谁能帮忙解释一下
  • 板块P1496 火烧赤壁
  • 楼主zuilp
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/23 20:31
  • 上次更新2024/11/23 22:31:01
查看原帖
题解没看懂,谁能帮忙解释一下
1165831
zuilp楼主2024/11/23 20:31

这是跟着题解敲的代码

#include<bits/stdc++.h>
#include<cstdlib>
using namespace std;
struct as{
    int r;
    int l;
    int ll;
    int lr;
    };
as all[30005];
int ma[30005];
int b[30005];
int sum[30005];
int ans;
int  main(){
    int n;                    cin>>n;
    for(int i=1;i<=n;i++)     cin>>all[i].l>>all[i].r;
    for(int i=1;i<=n;i++)     b[i]=all[i].l,b[i+n]=all[i].r;
    sort(b+1,b+2*n+1);
    int N=unique(b+1,b+1+2*n)-b-1;
    for(int i=1;i<=n;i++){
        all[i].ll=lower_bound(b+1,b+1+N,all[i].l)-b;
        all[i].lr=lower_bound(b+1,b+1+N,all[i].r)-b;
    }
    for(int i=1;i<=n;i++)ma[all[i].ll+1]++,ma[all[i].lr+1]--;
    for(int i=1;i<=N;i++)sum[i]+=sum[i-1]+ma[i];
    long long int ans=0;
    int l,r;
    for(int i=1;i<=N;i++){
        if(sum[i-1]==0&&sum[i]!=0)l=i-1;
        if(sum[i+1]==0&&sum[i]!=0){
            r=i;
            ans+=b[r]-b[l];
        }
    }
    cout<<ans;
}

就是第27行对差分数组进行操作时,为什么要将左端点+1的值++,然后在后面32行查找左端点时又把找到的左端点减一再计算。这不多次一举吗?但我把这两行改了又会出现一个wa的点


2024/11/23 20:31
加载中...