提高+省选-专题[二分][前缀和]：P1314 聪明的质监员

· · 题解

我这里推荐一下我的博客

在博客里观看更美观哦~

题目

华丽的分割线

解析

单调性

对于一个参数W,W越大,可选的值就越少,Y的值也越小

反过来,W越小,Y越大,如果Y是W的函数,那么该函数单调递减

可以考虑二分W,找到距离S最近的Y值

图像如下

这个函数奇怪之处在于它在S附近不连续

我们需要比较S附近那两个点与S的距离

在我的二分写法中这两个点从左到右分别为r,l

函数值

现在对于给定的W,如何用O(n)时间求出Y

先预处理出sum[i],和num[i],

sum[i]表示1~i中所有wi>=W的vi之和,num[i]则表示个数

i从1到n枚举,若wi<W,则sum[i]=sum[i-1],num[i]=num[i-1]

若wi>=W,则sum[i]=sum[i-1]+v[i],num[i]=num[i-1]+1

对于每个区间li,ri,ans+=(sum[ri]-sum[li-1])*(num[ri]-num[li-1])

返回ans即可

二分

初始化l=0,r=1e6,若f(mid)>s，则l向上移动,l=mid+1

否则r向下移动,r=mid-1,循环条件为l<=r

也就是说,当r>l时停止,所以左面的点为r,右面为l

ans=min(labs(f(l)-s),labs(f(r)-s))

代码

#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
const int N=1001000;
template<class T>
void read(T &x)
{
    x=0;
    T f;
    f=1;
    char c;
    c=getchar();
    while((c<'0'||c>'9')&&c!='-')
    {
        c=getchar();
    }
    if(c=='-')
    {
        f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    x=x*f;
}
int w[N],v[N],L[N],R[N],n,m;
ll s,sum[N],num[N];
ll check(ll W)
{
    int i;
    ll ans;
    ans=0;
    for(i=1;i<=n;i++)
    {
        if(w[i]<W)
        {
            num[i]=num[i-1];
            sum[i]=sum[i-1];
        }
        else
        {
            sum[i]=sum[i-1]+v[i];
            num[i]=num[i-1]+1;
        }
    }
    for(i=1;i<=m;i++)
    {
        ans+=(sum[R[i]]-sum[L[i]-1])*(num[R[i]]-num[L[i]-1]);
    }
    return ans;
}
inline ll labs(ll a)
{
    return a>0 ? a : -a;
}
int main()
{
    int i;
    ll l,r,mid,ans;
    read(n);
    read(m);
    read(s);
    for(i=1;i<=n;i++)
    {
        read(w[i]);
        read(v[i]);
    }
    for(i=1;i<=m;i++)
    {
        read(L[i]);
        read(R[i]);
    }
    l=0;
    r=1e6;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(mid)>s)
        {
            l=mid+1;
        }
        else
        {
            r=mid-1;
        }
    }
    ans=labs(check(l)-s);
    if(ans>labs(check(r)-s))
    {
        ans=labs(check(r)-s);
    }
    printf("%lld",ans);
}