题解 P1314 【聪明的质监员】

wshl · 2019-12-08 09:36:54 · 题解

• 题解：本题主要考查二分+前缀和。
• 简要题意：n个矿石,从1-n有重量w_i以及价值v_i​。给定区间[L_i,R_i],选出一个参数W,检验值Y_i= \sum\ 1* \sum\ v_j,w_j>=W，且Y=Y_1+Y_2+....+Y_m。
• 给标准值S,使得S−Y的绝对值最小，请你求出这个最小值。
• 1.二分：我们可以知道当W增大时，选的矿石越少，Y的值减小；当W减小时，选的矿石越多，Y的值增大。所以：
• (1).当Y=S时，Y-S==0；
• (2).当Y>S时，需要增大W来减小Y；
• (3).当Y<S时，需要减小W来增大Y。
• 2.前缀和：因为这里是两个区间和再相乘，所以用前缀和求值。
• 区间数量：t[i].num=t[i-1].num+1;
• 区间价值：t[i].v=t[i-1].v+e[i].v;
• 注意：本题数据很大，开long long，ans值要赋很大

代码如下：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
struct N
{
    long long num,v;
}t[233333];
struct E
{
    long long w,v;
}e[233333];
long long n,m,S,maxn=-0x3f3f,minn=0x3f3f3f,ans=0x3f3f3f3f3f3f3f,sum;
int l[233333],r[233333];
bool check(int W)
{
    memset(t,0,sizeof(t));
    long long Y=0;sum=0;
    for(int i=1;i<=n;i++)
    if(e[i].w>=W)
    {
        t[i].num=t[i-1].num+1;
        t[i].v=t[i-1].v+e[i].v;
    }
    else 
    {
        t[i].num=t[i-1].num;
        t[i].v=t[i-1].v;
    }
    for(int i=1;i<=m;i++)
        Y+=(t[r[i]].v-t[l[i]-1].v)*(t[r[i]].num-t[l[i]-1].num);
    sum=abs(S-Y);
    if(Y>S)return 1;
    else return 0;
}
int main()
{
    cin>>n>>m>>S;
    for(int i=1;i<=n;i++)
    {
        cin>>e[i].w>>e[i].v;
        maxn=max(maxn,e[i].w);
        minn=min(minn,e[i].w);
    }
    for(int i=1;i<=m;i++)
    cin>>l[i]>>r[i];
    int left=minn;int right=maxn;
    while(left<=right)
    {
        int mid=left+right>>1;
        if(check(mid))left=mid+1;
        else right=mid-1;
        if(sum<ans)ans=sum;
    }
    cout<<ans<<endl;
    return 0;
}