P1314 聪明的质监员

拼搏现实的明天。 2021-12-05 04:53 227阅读 0赞

原题连接 [ https://www.luogu.org/problemnew/show/P1314][https_www.luogu.org_problemnew_show_P1314]

![1617486-20190710092304820-1047400394.png][]

![1617486-20190710092337526-1365850973.png][]

![1617486-20190710092351489-2081715308.png][]

![1617486-20190710092417326-1813303287.png][]

首先题号好评QwQ~ 1314

乍一看此题，发现题目好像有点难理解，先带大家理解一下吧：

**意思就是：我们要在第 i 个区间 \[ Li , Ri \] 里找到所有的 j，使得 wj >= W，求出这些 j 的价值总和及符合条件的 j 的个数，那么这个区间的贡献就是这个价值总和乘上 j 的个数，然后我们要算所有区间的贡献的总和 Y ，最后输出 Y - S 的绝对值的最小值，其中 W 可以自己定 。**

既然 W 可以自己定，那么一个很显然的思路就是我们二分枚举 W，看看哪个 W 最合适不就好啦？

**枚举的上下界**

我们再回头看那个公式，显然若 W 变大，则 Y 变小（符合条件的 j 的数量少了）； 若 W 变小，则 Y 变大；

那么如果 W 一直变小，直到所有矿石的 wi 都大于我们枚举的这个 W 的话，那么不就是所有的矿石都被我们给选上了？这时候就会产生最大的 Y；

同理，当 W 比所有矿石的 wi 都大时，所有的矿石我们都没选，这时候就会产生最小的 Y ；

所以我们便得出来上下界：

下界：最小的 wi \- 1 ；

上界：最大的 wi \+ 2，这里为什么是 + 2 呢？因为 + 1就是所有矿石都不选的情况，我们枚举的时候也要考虑到这种情况。所以再 + 1 就囊括了所有的情况了；

for(int i=1;i<=n;i++)
        {
            a[i].w=read();
            a[i].v=read();
            if(a[i].w>maxn_w) maxn_w=a[i].w;       //找最大重量 
            if(a[i].w<minx_w) minx_w=a[i].w;       //找最小重量 
        }
        for(int i=1;i<=m;i++)                      //m个区间 
        {
            nl[i]=read();
            nr[i]=read();
        }
        long long left=minx_w-1;                   //找上下界,这样就能包含所有情况哦 
        long long right=maxn_w+2;

**二分过程**

当我们枚举的 W 求出的 Y 过大时，我们应该增大 W 来使得 Y 变小来尽量接近 S；当我们枚举的 W 求出的 Y 过小时，我们应该减小 W 来使得 Y 变大来尽量接近 S；然后我们在求过过程中对 | Y - S | 一直取min 就行了。

**求前缀和**

最后一部分就是求每个区间的贡献，显然我们要求出每个区间符合条件的 j 的个数和价值总和，如果我们对于每个区间我们都要 O（n）的枚举一遍的话， 总的时间复杂度应该是 O（nm log n），log n 是二分次数。对于 2e6 的数据，显然炸的妥妥的，那怎么办呢？

我们可以用前缀和鸭，对于我们枚举的每个 W ，我们都先预处理出 价值总和 ，符合条件的个数 这两个前缀和，然后每个区间我们 O（1）算出其贡献值，这样的时间复杂度应该是 O（（n+m） log n），比较保险~

对于上面的时间复杂度的估算，本蒟蒻很可能算错了，若发现错误请大佬们指出，感激不尽QwQ~

那么怎么求前缀和？

我们设： pre\_num \[ i \] 为第 1 个矿石到第 i 个矿石中符合条件的矿石数（条件：wj >= W），pre\_v \[ i \] 为第 1 个矿石到第 i 个矿石中所有符合条件的矿石的价值总和。

那么我们可以得出递推方程（状态转移方程）：

for(int i=1;i<=n;i++)
        {
            if(a[i].w>=W)                            //如果第i个矿石满足条件 
            {
                pre_num[i]=pre_num[i-1]+1;           //在上一个的基础上加上自己本身 
                pre_v[i]=pre_v[i-1]+a[i].v;
            }
            else                                     //不满足条件的话 
            {
                pre_num[i]=pre_num[i-1];             //继承上一个 
                pre_v[i]=pre_v[i-1];            
            }
        }

这个还是比较显然的吧QwQ~

**算区间贡献**

前缀和做差大家应该都会，我们有了1~n的前缀和了，那么我们求区间 \[ Li , Ri \] 内的符合条件的矿石数，就是区间 \[ 1 , Ri \] 内符合条件的矿石数减去区间 \[ 1 , Li -1\] 内符合条件的矿石数，求区间的价值总和同理：

for(int i=1;i<=m;i++)                         //m个区间
        {
            Y+=(pre_num[nr[i]]-pre_num[nl[i]-1])*(pre_v[nr[i]]-pre_v[nl[i]-1]);   //求每个区间的贡献和 
        }

上完整的AC代码：

#include<iostream>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    long long read()
    {
        char ch=getchar();
        long long a=0,x=1;
        while(ch<'0'||ch>'9')
        {
            if(ch=='-') x=-x;
            ch=getchar();
        }
        while(ch>='0'&&ch<='9')
        {
            a=(a<<3)+(a<<1)+(ch-'0');
            ch=getchar();
        }
        return a*x;
    }
    long long n,m,l,r;
    long long pre_num[2000001];
    long long nl[2000001],nr[2000001];
    long long maxn_w,minx_w,minx,S;
    long long pre_v[2000001];
    struct node
    {
        long long w,v;           //重量w,价值v 
    }a[2000001];
    int work(long long W)        //我们枚举的W 
    {
        for(int i=1;i<=n;i++)
        {
            pre_num[i]=0;
            pre_v[i]=0;
        }
        for(int i=1;i<=n;i++)                        //预处理 
        {
            if(a[i].w>=W)                            //如果第i个矿石满足条件 
            {
                pre_num[i]=pre_num[i-1]+1;           //在上一个的基础上加上自己本身 
                pre_v[i]=pre_v[i-1]+a[i].v;
            }
            else                                     //不满足条件的话 
            {
                pre_num[i]=pre_num[i-1];             //继承上一个 
                pre_v[i]=pre_v[i-1];            
            }
        }
        long long Y=0;
        for(int i=1;i<=m;i++)                         //m个区间
        {
            Y+=(pre_num[nr[i]]-pre_num[nl[i]-1])*(pre_v[nr[i]]-pre_v[nl[i]-1]);   //求每个区间的贡献和 
        } 
        long long s=Y-S;
        if(s<0) s=-s;                                 //手写取绝对值,用函数总有一堆奇怪的错误
        if(s<minx) minx=s;                            //更新答案 
        if(Y>S) return 1;                             //Y太大,需要增大W来减小Y 
        if(Y<S) return 0;                             //Y太小,需要减小W来增大Y 
        if(Y==S) return -1;                           //正好,一定是最优解 
    }
    int main()
    {
        n=read();m=read();S=read();
        maxn_w=-1314;minx_w=1e18;minx=1e18;
        for(int i=1;i<=n;i++)                       
        {
            a[i].w=read();
            a[i].v=read();
            if(a[i].w>maxn_w) maxn_w=a[i].w;       //找最大重量 
            if(a[i].w<minx_w) minx_w=a[i].w;       //找最小重量 
        }
        for(int i=1;i<=m;i++)                      //m个区间 
        {
            nl[i]=read();
            nr[i]=read();
        }
        long long left=minx_w-1;                   //找上下界,这样就能包含所有情况哦 
        long long right=maxn_w+2;
        while(left<=right)
        {
            long long mid=(left+right)>>1;
            int p=work(mid);                 
            if(p==1) left=mid+1;
            if(p==0) right=mid-1;
            if(p==-1) break;                     //找到了最优解,不必再搜了 
        }
        printf("%lld",minx);
        return 0;
    }

转载于:https://www.cnblogs.com/xcg123/p/11162052.html

[https_www.luogu.org_problemnew_show_P1314]: https://www.luogu.org/problemnew/show/P1314
[1617486-20190710092304820-1047400394.png]: /images/20211205/253d92165958499db6244db7225331b3.png
[1617486-20190710092337526-1365850973.png]: /images/20211205/636d72ff5cf44cbb9372fd6fd0aa10b8.png
[1617486-20190710092351489-2081715308.png]: /images/20211205/a9346f0a84f745719fb5ed87f9c0bf94.png
[1617486-20190710092417326-1813303287.png]: /images/20211205/e8494a29ffee4e9a9f0ff7e59cc37f2e.png