D. Frets On Fire 前缀和+二分

时间：2024-09-30 15:04:20

这个题真的难了我一天了，这种方法一开始没想出来，后来看了题解后明白了大致思路开始自己做但是！！！但是自己实现的时候老是一些细节出错！！！，调bug调了得有一个小时，蠢死了，这道题我一定要好好总结，总结为什么会卡壳，这要是比赛的签到题的话我得哭死！！！！！

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+;

unsigned long long a[maxn];

unsigned long long c[maxn];

unsigned long long sum[maxn];

set<unsigned long long> s;

int main()

{

    int n;

    cin>>n;

    for(int i=; i<=n; i++)

    {

        unsigned long long t;

        cin>>t;

        s.insert(t);

    }

    int cnt=;

    for(auto i:s)

        a[++cnt]=i;

    for(int i=; i<=cnt-; i++)

        c[i]=a[i+]-a[i];

    cnt--;

    sort(c+,c++cnt);

    for(int i=; i<=cnt; i++)

        sum[i]=sum[i-]+c[i];

    int q;

    cin>>q;

    while(q--)

    {

        unsigned long long l,r;

        cin>>l>>r;

        unsigned long long t=r-l;

        unsigned long long pos;

        unsigned long long ans=;

        pos=upper_bound(c+,c++cnt,t)-c;

        ans+=+t;

        ans+=(sum[pos-]);

        ans+=(cnt-pos+)*(t+);

        cout<<ans<<endl;

    }

}

读题之后我的最直接的思路是把这n个数，去重排序，然后是比较两两之间的长度与r-l的区间长度的关系然后一直累加出答案。如下超时代码。

我应该要注意到这两两之间的差值也是可以排序的，排完序之后只要在小于等于r-l的区间长度的都是我下面if语句的第一条，大于r-l区间长度的都是else语句的内容，这个判断可以二分来实现，同时对于小于等于区间长度的可以用预先求出前缀和来快速计算。

#include<bits/stdc++.h>

using namespace std;

set<unsigned long long> s;

const int maxn=1e5+;

unsigned long long a[maxn];

unsigned long long b[maxn];

int main()

{

    int n;

    cin>>n;

    for(int i=; i<=n; i++)

        cin>>a[i];

    int q;

    cin>>q;

    while(q--)

    {

        unsigned long long l,r;

        s.clear();

        memset(b,,sizeof(b));

        cin>>l>>r;

        for(int i=; i<=n; i++)

            s.insert(a[i]+l);

        unsigned long long t=r-l;

        int cnt=;

        for(auto i:s)

            b[++cnt]=i;

        unsigned long long ans=;

        for(int i=; i<=cnt-; i++)

        {

            if((b[i]+t)>=b[i+])

                ans+=b[i+]-b[i];

            else

                ans+=t+;

        }

        ans+=t+;

        printf("%lld\n",ans);

    }

}

相关文章