星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

题解 P1314 【聪明的质监员】

posted on 2017-09-12 21:41:02 | under 题解 |

博客即是洛谷blog。

本题是一个比较明显的二分题,显然可以看出来这个标准值S是可以二分的,之后如果暴力O(nmlog1e6)就是50分。

但我们显然不用暴力,这里我们可以先预扫一遍数组,并用前缀和存w和v,之后再一个O(m)暴力判断就可以了。

和大于标准时加大l以加大mid,小于时减少r。

并一定要注意l和r的初始大小,l为所有值中最小-1虽然貌似不减也可以过,r为最大值+1。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#define neko 300010
#define f(i,a,b) for(register int i=a;i<=b;++i)
typedef long long ll;
struct node
{
    int l,r;
}q[neko];
int n,m,l,r,mid,minn=1000000000,maxn,w[neko],c[neko];
ll stdd,sum,ans=1e13,v[neko],s[neko];
int main()
{
    int i,j;
    scanf("%d%d%lld",&n,&m,&stdd);
    f(i,1,n)scanf("%d%lld",&w[i],&v[i]),minn=std::min(minn,w[i]),maxn=std::max(maxn,w[i]);
    l=minn-1,r=maxn+1;
    f(i,1,m)scanf("%d%d",&q[i].l,&q[i].r);
    while(l<r)
    {
        mid=(l+r)>>1,sum=0,memset(c,0,sizeof(c)),memset(s,0,sizeof(s));
        f(i,1,n)
        {
            if(w[i]>=mid)c[i]=c[i-1]+1,s[i]=s[i-1]+v[i];
            else c[i]=c[i-1],s[i]=s[i-1];
        }
        f(i,1,m)sum+=(c[q[i].r]-c[q[i].l-1])*(s[q[i].r]-s[q[i].l-1]);
        //printf("%d %d %d %d\n",l,r,mid,sum);
        if(llabs(stdd-sum)<ans)ans=llabs(stdd-sum);
        if(sum>stdd)l=mid+1;
        else r=mid;
    }printf("%lld\n",ans);
    return 0;
}
O(m(n)log1e6)。