P1314 聪明的质监员

题目描述

小T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 n 个矿石，从 1 到 n 逐一编号，每个矿石都有自己的重量 \(w_i\) 以及价值 \(v_i\) 。检验矿产的流程是：

1 、给定 m 个区间 \([L_i,R_i]\) ；

2 、选出一个参数 W ；

3 、对于一个区间 \([L_i,R_i]\)，计算矿石在这个区间上的检验值 \(Y_i\) ：

这批矿产的检验结果 YYY 为各个区间的检验值之和。即： \(Y_1+Y_2...+Y_m\)

若这批矿产的检验结果与所给标准值 SSS 相差太多，就需要再去检验另一批矿产。小T不想费时间去检验另一批矿产，所以他想通过调整参数W 的值，让检验结果尽可能的靠近标准值 S ，即使得 \(S-Y\) 的绝对值最小。请你帮忙求出这个最小值。

输入输出格式

输入格式：

第一行包含三个整数 n,m,Sn,m,Sn,m,S ，分别表示矿石的个数、区间的个数和标准值。

接下来的 nnn 行，每行 222 个整数，中间用空格隔开，第 i+1i+1i+1 行表示 iii 号矿石的重量 wiw_iwi 和价值 viv_ivi 。

接下来的 mmm 行，表示区间，每行 222 个整数，中间用空格隔开，第 i+n+1i+n+1i+n+1 行表示区间 [Li,Ri][L_i,R_i][Li,Ri] 的两个端点 LiL_iLi 和 RiR_iRi 。注意：不同区间可能重合或相互重叠。

输出格式：

一个整数，表示所求的最小值。

输入输出样例

输入样例#1： 复制

5 3 15

1 5

2 5

3 5

4 5

5 5

1 5

2 4

3 3

输出样例#1： 复制

【数据范围】

对于 \(10\%\) 的数据，有 \(1 ≤n ,m≤10\) ；

对于 \(30\%\) 的数据，有 \(1 ≤n ,m≤500\) ；

对于 \(50\%\) 的数据，有 \(1 ≤n ,m≤5,000\) ；

对于 \(70\%\) 的数据，有 \(1 ≤n ,m≤10\) ；

对于 \(100\%\) 的数据，有 \(1 ≤n ,m≤200,000,0 < w_i,v_i≤10^6,0 < S≤10^{12},1 ≤L_i ≤R_i ≤n\) 。

二分答案 \(W\) 求出 \(Y\) 和 \(S\) 比较，如果 \(Y>S\) 把右端点左移至 \(mid-1\)，如果 \(Y<S\) 把左端点右移至 \(mid+1\)

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

using namespace std;

int w[1000008],v[1000008],i,m,n,j,k,l[1000008],r[1000008],maxx;

long long d[1000008],t[1000008],ans=2147483647000000,s;

void add(int now,int k,long long *b)

{

	for(int i=now;i<=n;i+=(i&(-i))) b[i]+=k;

}

long long ff(int now,long long *b)

{

	long long ans=0;

	for(int i=now;i>0;i-=(i &(-i))) ans+=b[i];

	return ans;

}

long long dfs(int ww)

{

	long long s=0,z=0,Y=0;

	memset(d,0,sizeof(d));

	memset(t,0,sizeof(t));

	for(int i=1;i<=n;i++)

		if(w[i]>=ww) add(i,1,d),add(i,v[i],t);

	for(int i=1;i<=m;i++)

		Y+=((ff(r[i],d)-ff(l[i]-1,d))*(ff(r[i],t)-ff(l[i]-1,t)));

	return Y;

}

void ef(int ll,int rr)

{

	while(ll<=rr)

	{

		int mid=(ll+rr+1)/2;

		long long y=dfs(mid);

		ans=min(ans,abs(y-s));

		if(s>y) rr=mid-1;

		else ll=mid+1;

		if(s==y) return;

	}

}

int main()

{

	scanf("%d%d%lld",&n,&m,&s);

	for(i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]),maxx=max(maxx,w[i]);

	for(i=1;i<=m;i++) scanf("%d%d",&l[i],&r[i]);

	ef(0,maxx+1);

	printf("%lld",ans);

}

巴特西

P1314 聪明的质监员

题目描述

输入输出格式

输入输出样例

最新文章

热门文章