全WA求助

P1047 [NOIP2005 普及组] 校门外的树

__hqt__ @ 2023-10-31 14:01:40

题目：P1047
算法：差分
代码：

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int a[100001],b[100001];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int l,m,ans=0;
    cin>>l>>m;
    a[1]=1;
    for(int i=1;i<=m;i++)
    {
        int t1,t2;
        cin>>t1>>t2;
        a[t1]--;
        a[t2+1]++;
    }
    for(int i=1;i<=l;i++)
    {
        b[i]=b[i-1]+a[i];
        if(b[i]<=0)
        {
            ans++;
        }
    }
    cout<<ans<<endl;
}

by wanglexi @ 2023-10-31 17:52:49

这题卡差分qwq......

  • 对于 20\% 的数据，保证区域之间没有重合的部分。

说明100\%的数据由重复部分。

其实正解是直接模拟。

每次砍树 O(l) ，总共砍 m 次树，最后枚举所有位置进行统计 O(l)，总体复杂度 O(ml)。

另外，特别注意审题：

数轴上的每个整数点，即 0,1,2,\dots,l，都种有一棵树。

所以是 0\sim l 的点。

```cpp #include<bits/stdc++.h> using namespace std; int l,m,u,v,a[10005],ans;//a[i]:第i棵树被挖走了吗？0:没有 1:有 int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>l>>m; while(m--){ cin>>u>>v; for(int i=u;i<=v;i++) a[i]=1;//挖走 } for(int i=0;i<=l;i++) if(a[i]==0) ans++; cout<<ans; return 0; } ```

by wanglexi @ 2023-10-31 17:53:13

@hqt_

by __hqt__ @ 2023-10-31 19:51:33

谢大佬，此贴已解决

|