Luogu 1314 【NOIP2011】聪明的质检员 （二分）
Description
小 T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有n个矿石，从 1 到n逐一编号，每个矿石都有自己的重量wi以及价值vi。检验矿产的流程是：
- 给定 m个区间[Li,Ri]；
- 选出一个参数W；
- 对于一个区间[Li,Ri]，计算矿石在这个区间上的检验值Yi：
\]
这批矿产的检验结果Y为各个区间的检验值之和。即：
\]
若这批矿产的检验结果与所给标准值 S相差太多，就需要再去检验另一批矿产。小 T 不想费时间去检验另一批矿产，所以他想通过调整参数W的值，让检验结果尽可能的靠近标准值 S，即使得S−Y的绝对值最小。请你帮忙求出这个最小值。
Input
第一行包含三个整数n，m，S，分别表示矿石的个数、区间的个数和标准值。
接下来的n 行，每行2 个整数，中间用空格隔开，第i+1 行表示i 号矿石的重量wi 和价值vi 。
接下来的m 行，表示区间，每行2 个整数，中间用空格隔开，第i+n+1 行表示区间[Li,Ri]的两个端点Li 和Ri。注意：不同区间可能重合或相互重叠。
Output
输出只有一行，包含一个整数，表示所求的最小值。
Sample Input
5 3 15
1 5
2 5
3 5
4 5
5 5
1 5
2 4
3 3
Sample Output
10
Http
Luogu:https://www.luogu.org/problem/show?pid=1314
Source
二分
题目大意
给出n组二元组和m个区间，现在定义一个区间上的检验结果为这个区间上所有二元组中，第一个数大于W的二元组的第二个数*这些二元组的个数。定义整个的检验结果为给定的m个区间的检验结果之和。将整个的检验结果与一给定的标准值相比，两者之差的绝对值即为这个W对应的答案。现在求W让这个答案最小，求出最小值。
解决思路
讲题目的思路理清后，我们可以想到二分W的值。因为这个整个的检验结果与W是保持单调的，若W增大，则检验结果变小，反之变大。
所以我们可以二分W，每次二分出W后，计算一下其检验结果，若检验结果大于给定的S，则将左端点右移，否则将右端点左移。注意，最后输出的答案是每一次的检验结果与S作差的绝对值的最小值。
至于计算检验结果，因为题中给定的都是区间，所以我们可以每找出一个W后\(O(n)\)计算一下前缀和，然后\(O(1)\)地计算区间和。
注意，所有的变量都要开long long。
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
const int maxN=300000;
const int inf=2147483647;
ll n,m,S;
ll Ans=1e13;
ll Weight[maxN];
ll Value[maxN];
ll Rangel[maxN];
ll Ranger[maxN];
ll Sum[maxN];
ll Cnt[maxN];
ll read();
bool Solve(ll nowW);
int main()
{
n=read();
m=read();
S=read();
ll l=0,r=0;
for (int i=1;i<=n;i++)
{
Weight[i]=read();
Value[i]=read();
r=max(r,Weight[i]);//r取最大值
}
for (int i=1;i<=m;i++)
{
Rangel[i]=read();
Ranger[i]=read();
}
r=r+100;//为了防止出错，扩大上限
while (l<=r)//二分W
{
ll mid=(l+r)>>1;
if (Solve(mid))
l=mid+1;
else
r=mid-1;
//cout<<l<<" "<<r<<endl;
}
cout<<Ans<<endl;
return 0;
}
ll read()
{
ll x=0;
char ch=getchar();
while ((ch<'0')||(ch>'9'))
ch=getchar();
while ((ch>='0')&&(ch<='9'))
{
x=x*10+ch-48;
ch=getchar();
}
return x;
}
bool Solve(ll nowW)
{
Sum[0]=0;
Cnt[0]=0;
for (int i=1;i<=n;i++)//计算前缀和，Sum是价值之和，Cnt是人数之和
{
Sum[i]=Sum[i-1]+((Weight[i]>=nowW)?(Value[i]):0);
Cnt[i]=Cnt[i-1]+((Weight[i]>=nowW)?1:0);
}
ll tot=0;
for (int i=1;i<=m;i++)//计算区间贡献之和
tot+=(Sum[Ranger[i]]-Sum[Rangel[i]-1])*(Cnt[Ranger[i]]-Cnt[Rangel[i]-1]);
Ans=min(Ans,abs(tot-S));//取最优值
if (tot>=S)
return 1;
return 0;
}