（1）聪明的质检员
小 T 是一名质量监督员，最近负责检验一批矿产的质量。
这批矿产共有 n 个矿石，从 1 到 n 逐一编号，每个矿石都有自己的重量 wi 以及价值 vi。
检验矿产的流程是：
1、给定 m 个区间 [Li，Ri]；
2、选出一个参数 W；
3、对于一个区间 [Li，Ri]，计算矿石在这个区间上的检验值 Yi ：
QQ截图20190314005531.png
这批矿产的检验结果 Y 为各个区间的检验值之和。
即：Y = Y1+Y2+…+Ym
若这批矿产的检验结果与所给标准值 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≤n,m≤200000,
0<wi,vi≤106,
0<S≤1012,
1≤Li≤Ri≤n
输入样例：
5 3 15
1 5
2 5
3 5
4 5
5 5
1 5
2 4
3 3
输出样例：
10
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 200010;
int n, m;
LL S;
int w[N], v[N];
int l[N], r[N];
int cnt[N];
LL sum[N];
LL get(int W)
{
for (int i = 1; i <= n; i ++ )
if (w[i] >= W)
{
sum[i] = sum[i - 1] + v[i];
cnt[i] = cnt[i - 1] + 1;
}
else
{
sum[i] = sum[i - 1];
cnt[i] = cnt[i - 1];
}
LL res = 0;
for (int i = 0; i < m; i ++ ) res += (cnt[r[i]] - cnt[l[i] - 1]) * (sum[r[i]] - sum[l[i] - 1]);
return res;
}
int main()
{
scanf("%d%d%lld", &n, &m, &S);
for (int i = 1; i <= n; i ++ ) scanf("%d%d", &w[i], &v[i]);
for (int i = 0; i < m; i ++ ) scanf("%d%d", &l[i], &r[i]);
int l = 0, r = 1e6 + 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (get(mid) >= S) l = mid;
else r = mid - 1;
}
printf("%lld\n", min(abs(get(r) - S), abs(S - get(r + 1))));
return 0;
}
总结： Y 随 W 单调递减。
因此我们可以二分出距离 S 最近的值。
时间复杂度分析
总共二分 O(logW) 次，每次预处理前缀和的计算量是 O(N)，求 Y的计算量是 O(M)。因此总时间复杂度是 O(N+M)logW。
（2）借教室
在大学期间，经常需要租借教室。
大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。
教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。
面对海量租借教室的信息，我们自然希望编程解决这个问题。
我们需要处理接下来 n 天的借教室信息，其中第 i 天学校有 ri 个教室可供租借。
共有 m 份订单，每份订单用三个正整数描述，分别为 dj,sj,tj，表示某租借者需要从第 sj 天到第 tj 天租借教室（包括第 sj 天和第 tj 天），每天需要租借 dj 个教室。
我们假定，租借者对教室的大小、地点没有要求。
即对于每份订单，我们只需要每天提供 dj 个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。
借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。
如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。
这里的无法满足指从第 sj 天到第 tj 天中有至少一天剩余的教室数量不足 dj 个。
现在我们需要知道，是否会有订单无法完全满足。
如果有，需要通知哪一个申请人修改订单。
输入格式
第一行包含两个正整数 n,m，表示天数和订单的数量。
第二行包含 n 个正整数，其中第 i 个数为 ri，表示第 i 天可用于租借的教室数量。
接下来有 m 行，每行包含三个正整数 dj,sj,tj，表示租借的数量，租借开始、结束分别在第几天。
每行相邻的两个数之间均用一个空格隔开。
天数与订单均用从 1 开始的整数编号。
输出格式
如果所有订单均可满足，则输出只有一行，包含一个整数 0。
否则（订单无法完全满足）输出两行，第一行输出一个负整数 −1，第二行输出需要修改订单的申请人编号。
数据范围
1≤n,m≤106,
0≤ri,dj≤109,
1≤sj≤tj≤n
输入样例：
4 3
2 5 4 3
2 1 3
3 2 4
4 2 4
输出样例：
-1
2
代码：
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6+10;
int n,m;
int r[N],d[N],s[N],t[N];
LL b[N];
bool check(int mid)
{
for(int i=1;i<=n;i++) b[i]=r[i]-r[i-1]; //差分数组初始化
for(int i=1;i<=mid;i++)
{
b[s[i]]-=d[i];
b[t[i]+1]+=d[i];
}
for(int i=1;i<=n;i++)
{
b[i]+=b[i-1];
if(b[i]<0)return true; //不满足
}
return false;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&r[i]);
for(int i=1;i<=m;i++)scanf("%d%d%d",&d[i],&s[i],&t[i]);
if(!check(m))
{
printf("0\n");
return 0;
}
int l=1;
int r=m;
while(l<r)
{
int mid=l+r>>1;
if(check(mid)) r=mid; //如果第i个人不满足，则答案在左边,找第一个不满足的人，因为他后面的全不满足
else l=mid+1;
}
printf("-1\n");
cout<<r;
return 0;
}
4、赶牛入圈
农夫约翰希望为他的奶牛们建立一个畜栏。
这些挑剔的畜生要求畜栏必须是正方形的，而且至少要包含 C 单位的三叶草，来当做它们的下午茶。
畜栏的边缘必须与 X，Y 轴平行。
约翰的土地里一共包含 N 单位的三叶草，每单位三叶草位于一个 1×1 的土地区域内，区域位置由其左下角坐标表示，并且区域左下角的 X,Y 坐标都为整数，范围在 1 到 10000 以内。
多个单位的三叶草可能会位于同一个 1×1 的区域内，因为这个原因，在接下来的输入中，同一个区域坐标可能出现多次。
只有一个区域完全位于修好的畜栏之中，才认为这个区域内的三叶草在畜栏之中。
请你帮约翰计算一下，能包含至少 C 单位面积三叶草的情况下，畜栏的最小边长是多少。
输入格式
第一行输入两个整数 C 和 N。
接下来 N 行，每行输入两个整数 X 和 Y，代表三叶草所在的区域的 X,Y 坐标。
同一行数据用空格隔开。
输出格式
输出一个整数，代表畜栏的最小边长。
数据范围
1≤C≤500,
C≤N≤500
输入样例：
3 4
1 2
2 1
4 1
5 2
输出样例：
4
代码：
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
int n, m;
PII points[N];
int sum[N][N];
vector<int> numbers;
bool check(int len)
{
for (int x1 = 1, x2 = 1; x2 < numbers.size(); x2 ++ )
{
while (numbers[x2] - numbers[x1 ] + 1 > len) x1 ++ ;
for (int y1 =1, y2 = 1; y2 < numbers.size(); y2 ++ )
{
while (numbers[y2] - numbers[y1 ] + 1 > len) y1 ++ ;
if (sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1] >= m)
return true;
}
}
return false;
}
int get(int x)
{
int l = 0, r = numbers.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (numbers[mid] >= x) r = mid;
else l = mid + 1;
}
return r;
}
// int get_id(int n)
// {
// return lower_bound(numbers.begin(), numbers.end(), n) - numbers.begin();
// }
int main()
{
cin >> m >> n;
numbers.push_back(0);
for (int i = 0; i < n; i ++ )
{
int x, y;
cin >> x >> y;
numbers.push_back(x);
numbers.push_back(y);
points[i] = {x, y};
}
sort(numbers.begin(), numbers.end());
numbers.erase(unique(numbers.begin(), numbers.end()), numbers.end());
for (int i = 0; i < n; i ++ )
{
int x = get(points[i].first), y = get(points[i].second);
sum[x][y] ++ ;
}
for (int i = 1; i < numbers.size(); i ++ )
for (int j = 1; j < numbers.size(); j ++ )
sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
int l = 1, r = 10000;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << r << endl;
return 0;
}
