首页 > 代码库 > vijos1740 聪明的质监员 （二分、区间求和）

vijos1740 聪明的质监员 （二分、区间求和）

2024-07-16 13:45:14   219人阅读

http://www.rqnoj.cn/problem/657

https://www.vijos.org/p/1740

P1740聪明的质检员
请登录后递交
标签：NOIP提高组2011[显示标签]
 

描述

小 T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有n个矿石，从1到n逐一编号，每个矿石都有自己的重量wi以及价值vi。检验矿产的流程是：
1、给定m个区间[Li，Ri]；
2、选出一个参数W；
3、对于一个区间[Li，Ri]，计算矿石在这个区间上的检验值Yi：
Yi = ∑1*∑vj，j∈[Li, Ri]且wj ≥ W，j是矿石编号
这批矿产的检验结果Y 为各个区间的检验值之和。即：Y = ∑Yi，i ∈[1, m]
若这批矿产的检验结果与所给标准值S相差太多，就需要再去检验另一批矿产。小T不想费时间去检验另一批矿产，所以他想通过调整参数W的值，让检验结果尽可能的靠近标准值S，即使得S-Y的绝对值最小。请你帮忙求出这个最小值。

格式

输入格式

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

接下来的n行，每行2个整数，中间用空格隔开，第i+1行表示i号矿石的重量wi和价值vi 。

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

输出格式

输出只有一行，包含一个整数，表示所求的最小值。

样例1

样例输入1[复制]

5 3 151 52 53 54 55 51 52 43 3

样例输出1[复制]

10

限制

1s

提示

样例说明：当W选4的时候，三个区间上检验值分别为20、5、0，这批矿产的检验结果为25，此时与标准值S相差最小为10。

对于10%的数据，有1 ≤ n，m ≤ 10；
对于30%的数据，有1 ≤ n，m ≤ 500；
对于50%的数据，有1 ≤ n，m ≤ 5,000；
对于70%的数据，有1 ≤ n，m ≤ 10,000；
对于100%的数据，有1 ≤ n，m ≤ 200,000，0 < wi, vi ≤ 10^6，0 < S ≤ 10^12，1 ≤ Li ≤ Ri ≤ n。

来源

NOIp2011提高组Day2第二题

大意：给你一排物品，有重量wi，价值vi，再给你一排区间。有一个W，对每个区间求Σ1*Σvi，两个Σ都是符合w[j]>=W的j，也就是若一个区间里有3个物品的w大于等于W，则这个区间的值为3*(w1+w2+w3)。要使各区间的这个值的和与给定值S的绝对值最小，求这个最小的绝对值。

题解：二分+区间求和。

因为各区间值的和随W单调递减，可以二分W。每次二分都要怒求好多区间的区间和，所以我们每次二分，都求一次根据这个W生成的前缀和，方便求区间和。

 1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set>10 #include<stack>11 #include<queue>12 using namespace std;13 #define ll long long14 #define usint unsigned int15 #define mz(array) memset(array, 0, sizeof(array))16 #define minf(array) memset(array, 0x3f, sizeof(array))17 #define REP(i,n) for(int i=0;i<(n);i++)18 #define FOR(i,x,n) for(int i=(x);i<=(n);i++)19 #define RD(x) scanf("%d",&x)20 #define RD2(x,y) scanf("%d%d",&x,&y)21 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)22 #define WN(x) printf("%d\n",x);23 #define RE  freopen("D.in","r",stdin)24 #define WE  freopen("1biao.out","w",stdout)25 26 const int maxn=222222;27 int w[maxn],v[maxn];28 int L[maxn],R[maxn];29 int n,m;30 ll S;31 32 ll ss[maxn],cn[maxn];33 34 void check(ll a[],int n){35     for(int i=0;i<n;i++)36         printf("%5lld ",a[i]);37     puts("");38 }39 40 ll gank(int W) {41     ll re=0;42     ss[0]=0;43     cn[0]=0;44     for(int i=1; i<=n; i++) {45         if(w[i-1]>=W) {46             ss[i]=ss[i-1]+v[i-1];47             cn[i]=cn[i-1]+1;48         } else {49             ss[i]=ss[i-1];50             cn[i]=cn[i-1];51         }52     }53     for(int i=0; i<m; i++) {54         re+=(cn[R[i]]-cn[L[i]-1])*(ss[R[i]]-ss[L[i]-1]);55 //      cout<<cn[R[i]]-cn[L[i]-1]<<‘*‘<<ss[R[i]]-ss[L[i]-1]<<endl;56     }57 //    check(ss,n+1);58 //    check(cn,n+1);59 //    printf("↑W=%d,re=%lld\n",W,re);60     return re;61 }62 63 int main() {64     int i,j,l,r,mid,maxr;65     while(scanf("%d%d%lld",&n,&m,&S)!=EOF) {66         maxr=0;67         REP(i,n) {68             scanf("%d%d",&w[i],&v[i]);69             maxr=max(maxr,w[i]+1);70         }71         REP(i,m) {72             scanf("%d%d",&L[i],&R[i]);73             //L[i]--;74             //R[i]--;75         }76         l=1;77         r=maxr;78         while(l<=r) {79             mid=(l+r)>>1;80             if(S>gank(mid)) r=mid-1;81             else l=mid+1;82         }83         //cout<<mid<<‘,‘<<l<<‘,‘<<r<<endl;84         ll t=abs(S-gank(mid));85         t=min(t,abs(S-gank(l)));86         t=min(t,abs(S-gank(r)));87         printf("%lld\n",t);88     }89     return 0;90 }
View Code

 


联系
我们