vijos P1740 聪明的质检员

题目大意:给你n个物品，每件物品有重量 W 和价值 V，给m个区间，和一个标准值。(n,m最大200000)

　　　　要求找到一个值x，使得m个所有区间的权值和与标准值的差的绝对值最小。单个区间权值计算公式(数目num=0，价值sum=0,若满足 Wi >= x ,则++num，sum+=Vi)

　　　　单个区间权值为num*sum

题目思路: 二分+前缀和

　首先权值和与X是递减关系，X越大所得值越小，我们容易想到二分，但是m个区间的比较判断怎么处理，如果直接模拟，复杂度最大可达 n^2logn 显然不行

　　　　其实我们可以，用前缀和的想法，用一个数组num 表示1~i 满足W>=x的个数，sum对应为满足条件的W对应的V之和，那么对于区间我们可直接O（1）得值

　　　　每次前缀处理O（n），所以总复杂度 nlogn ，还有此题需用long long 不然WA

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <cstring>

#include <stack>

#include <cctype>

#include <queue>

#include <string>

#include <vector>

#include<functional>

#include <set>

#include <map>

#include <climits>

#define lson root<<1,l,mid

#define rson root<<1|1,mid+1,r

#define fi first

#define se second

#define ping(x,y) ((x-y)*(x-y))

#define mst(x,y) memset(x,y,sizeof(x))

#define mcp(x,y) memcpy(x,y,sizeof(y))

using namespace std;

#define gamma 0.5772156649015328606065120

#define MOD 1000000007

#define inf 0x3f3f3f3f

#define N 200005

#define maxn 10000500

typedef pair<int,int> PII;

typedef long long LL;

LL n,m;

LL k,sta,l=-,r,ans=1ll<<;

struct Node{

    LL x,v;

}node[N];

struct Seg{

    LL x,y;

}seg[N];

LL num[N],sum[N];

bool match(LL x){

    for(LL i=;i<=n;++i){

        num[i]=num[i-];sum[i]=sum[i-];

        if(node[i].x>=x){++num[i];sum[i]+=node[i].v;}

    }

    LL temp=;

    for(LL i=;i<=m;++i){

        LL t1=seg[i].x,t2=seg[i].y;

        temp+=(sum[t2]-sum[t1-])*(num[t2]-num[t1-]);

    }

    temp=temp-sta;

    ans=min(ans,llabs(temp));

    return temp>=;

}

int main(){

    LL i,j,v;

    scanf("%lld%lld%lld",&n,&m,&sta);

    for(i=;i<=n;++i){scanf("%lld%lld",&node[i].x,&node[i].v);r=max(r,node[i].x);}

    for(i=;i<=m;++i){scanf("%lld%lld",&seg[i].x,&seg[i].y);}

    ++r;

    while(l<=r){

        LL mid=l+r>>;

        if(match(mid)){

            l=mid+;

        }

        else r=mid-;

    }

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

    return ;

}

巴特西

vijos P1740 聪明的质检员

最新文章

热门文章