【问题描述】
小 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 是矿石编号
j j
m
这批矿产的检验结果 Y 为各个区间的检验值之和。即： Y = ∑ Yi
i=1
若这批矿产的检验结果与所给标准值 S 相差太多，就需要再去检验另一批矿产。小 T
不想费时间去检验另一批矿产，所以他想通过调整参数 W 的值，让检验结果尽可能的靠近
标准值 S，即使得 S-Y 的绝对值最小。请你帮忙求出这个最小值。
【输入】
输入文件 qc.in。
第一行包含三个整数 n，m，S，分别表示矿石的个数、区间的个数和标准值。
接下来的 n 行，每行 2 个整数，中间用空格隔开，第 i+1 行表示 i 号矿石的重量 wi和价
值 vi。
接下来的 m 行，表示区间，每行 2 个整数，中间用空格隔开，第 i+n+1 行表示区间[Li,
Ri]的两个端点 Li和 Ri。注意：不同区间可能重合或相互重叠。
【输出】
输出文件名为 qc.out。
输出只有一行，包含一个整数，表示所求的最小值。
【输入输出样例】
qc.in
5 3 15
1 5
2 5
3 5
4 5
5 5
1 5
2 4
3 3
【输入输出样例说明】
qc.out
10
当 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≤106，0 < S≤1012，1≤Li≤Ri≤n。
讲解：
1.10%，这个最暴力的都可以吧
2.30%,n,m都很小，枚举w=(w1+1,w1,w2+1,w2,w3+1,w3,...,wn+1),算出y之后取最接近的即可，时间复杂度n*m*n
3.50% 用前缀和优化
我们要求m次区间和，而被算入其中的都是同一部分，那么就可以在每次算y之前先预处理出前缀和，然后对于m个区间的yi的计算为O(1)
时间复杂度O(n*m)
4.70% 二分+线段树优化
线段树优化其实要比前缀和好想，再加上二分答案
O(log(max(w))*m*logm)
5.100% 二分+前缀和优化
代码： //切忌：注意开long long , 包括 pre 前缀 ，ans , t , s;
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int MX=200010; int w[MX],v[MX],l[MX],r[MX]; long long pre_n[MX],pre_v[MX]; int left=0x3f3f3f3f,right,n,m; long long s,t,dif; bool ser(int W) { t=0; memset(pre_n,0,sizeof(pre_n)); memset(pre_v,0,sizeof(pre_v)); for(int i=1;i<=n;++i) { if(w[i]>=W) { pre_n[i]=pre_n[i-1]+1; pre_v[i]=pre_v[i-1]+v[i]; } else { pre_n[i]=pre_n[i-1]; pre_v[i]=pre_v[i-1]; } } for(int i=1;i<=m;++i) { t+=(pre_n[r[i]]-pre_n[l[i]-1]) * (pre_v[r[i]]-pre_v[l[i]-1]); } dif=llabs(t-s); if(t>s) return true; else return false; } int main() { scanf("%d%d %lld",&n,&m,&s); for(int i=1;i<=n;++i) { scanf("%d%d",&w[i],&v[i]); left=min(left,w[i]); right=max(right,w[i]); } for(int i=1;i<=m;++i) { scanf("%d%d",&l[i],&r[i]); } left-=1,right+=2; long long ans=0x3f3f3f3f3f; while(left<=right) { int mid=(left+right)>>1; if(ser(mid)) left=mid+1; else right=mid-1; if(dif<ans) ans=dif; } printf("%lld",ans); return 0; }
904 的惨痛，905 的一遍A！
#include<stdio.h> #include<algorithm> #define ll long long using namespace std; const int MX=200001; int n,m,left=0x3f3f3f3f,right=-1,w[MX],v[MX],l[MX],r[MX]; ll d,s,cs,pre_n[MX],pre_v[MX]; bool ask(int W) { cs=0; for(int i=1;i<=n;++i) { pre_n[i]=pre_n[i-1]; pre_v[i]=pre_v[i-1]; if(w[i]>=W) { pre_n[i]++; pre_v[i]+=v[i]; } } for(int i=1;i<=m;++i) cs+=(pre_n[r[i]]-pre_n[l[i]-1])*(pre_v[r[i]]-pre_v[l[i]-1]); d=llabs(cs-s); if(cs>s) return true; else return false; } int main() { scanf("%d%d%lld",&n,&m,&s); for(int i=1;i<=n;++i) { scanf("%d%d",&w[i],&v[i]); left=min(left,w[i]); right=max(right,w[i]); } for(int i=1;i<=m;++i) scanf("%d%d",&l[i],&r[i]); ll ans=0x3f3f3f3f3f; while(left<=right) { int mid=(left+right)>>1; if(ask(mid)) left=mid+1; else right=mid-1; if(d<ans) ans=d; } printf("%lld",ans); return 0; }