两题出自NOIP的肥常肥常肥肠经典的二分题目,学习二分时候,特别适合用来练手ヾ(•ω•`)o

一、借教室

题目描述

在大学期间,经常需要租借教室。大到院系举办活动,小到学习小组自习讨论,都需要向学校申请借教室。教室的大小功能不同,借教室人的身份不同,借教室的手续也不一样。

面对海量租借教室的信息,我们自然希望编程解决这个问题。

我们需要处理接下来 $n$ 天的借教室信息,其中第 $i$ 天学校有 $r_i$ 个教室可供租借。共有 $m$ 份订单,每份订单用三个正整数描述,分别为 $d_j,s_j,t_j$ ,表示某租借者需要从第 $s_j$ 天到第 $t_j$ 天租借教室(包括第 $s_j$ 天和第 $t_j$ 天),每天需要租借 $d_j$ 个教室。

我们假定,租借者对教室的大小、地点没有要求。即对于每份订单,我们只需要每天提供 $d_j$ 个教室,而它们具体是哪些教室,每天是否是相同的教室则不用考虑。

借教室的原则是先到先得,也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足,则需要停止教室的分配,通知当前申请人修改订单。这里的无法满足指从第 $s_j$ 天到第 $t_j$ 天中有至少一天剩余的教室数量不足 $d_j$ 个。

现在我们需要知道,是否会有订单无法完全满足。如果有,需要通知哪一个申请人修改订单。

输入格式

第一行包含两个正整数 $n,m$,表示天数和订单的数量。

第二行包含 $n$ 正整数,其中第 $i$ 个数为 $r_i$ ,表示第 $i$ 天可用于租借的教室数量。

接下来有 $m$ 行,每行包含三个正整数 $d_j,s_j,t_j$ ,表示租借的数量,租借开始、结束分别在第几天。

每行相邻的两个数之间均用一个空格隔开。天数与订单均用从 $1$ 开始的整数编号。

输出格式

如果所有订单均可满足,则输出只有一行,包含一个整数 $0$ 。否则(订单无法完全满足)输出两行,第一行输出一个负整数 $-1$ ,第二行输出需要修改订单的申请人编号。

输入输出样例

输入
4 3 
2 5 4 3 
2 1 3 
3 2 4 
4 2 4
输出
-1 
2

说明/提示

【输入输出样例说明】

第 $1$ 份订单满足后,$4$ 天剩余的教室数分别为 $0,3,2,3$。第 $2$ 份订单要求第 $2$ 天到第 $4$ 天每天提供 $3$ 个教室,而第 $3$ 天剩余的教室数为 $2$,因此无法满足。分配停止,通知第 $2$ 个申请人修改订单。

【数据范围】

$1 \le n,m \le 10^6$,

$0 \le r_i,d_j \le 10^9$,

$1 \le s_j \le t_j \le n$

思路

不难发现,随着订单数量的增加,每天可用的教室的数量一定单调下降,所以这里很容易用二分来枚举第一天出现不满足的情况的订单数量。

还有一个问题就是如何快速的求经过若干订单之后,每天剩余的教室数量。

每个订单的操作是将 $[L_i, R_i]$ 减去 $d_i$ ,所以可以用差分来处理

参考代码

差分模板

给区间[l, r]中的每个数加上c:
B[l] += c, B[r + 1] -= c

完整代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int n, m;
int r[N], d[N], s[N], t[N];
int 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 false;
    }

    return true;
}

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))
    {
        puts("0");
        return 0;
    }

    int l = 0, r = m;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }

    printf("-1\n%d\n", l);
    return 0;
}

原题链接:[NOIP2012 提高组] 借教室


二、聪明的质监员

题目描述

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

1、给定 $m$ 个区间 $[l_i,r_i]$;

2 、选出一个参数 $W$;

3 、对于一个区间 $[l_i,r_i]$,计算矿石在这个区间上的检验值 $y_i$ :

image.png

其中 $j$ 为矿石编号。

这批矿产的检验结果 $y$ 为各个区间的检验值之和。即:$\sum_iy_i$

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

输入格式

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

接下来的 $n$ 行,每行两个整数,中间用空格隔开,第 $i+1$ 行表示 $i$ 号矿石的重量 $w_i$ 和价值 $v_i$。

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

输出格式

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

输入输出样例

输入
5 3 15 
1 5 
2 5 
3 5 
4 5 
5 5 
1 5 
2 4 
3 3 
输出
10

说明/提示

【输入输出样例说明】

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

【数据范围】

$1 \le n,m \le 200000$,

$1 \le w_j, v_j \le 10^6$,

$0 \le s \le 10^{12}$,

$1 \le l_i \le r_i \le n$

思路

解释以下上面哪个公式的意思:区间$[L_i, R_i]$中大于等于 $W$的个数乘以价值之和,样例区间$[1,5]$中$w_i \ge W$的有$4$号矿石和$5$号矿石,共两个,它们的价值和为$5 + 5 = 10$,所以最终区间$[1,5]$的检验值为$2 \times 10 = 20$。

观察题意,我们可以发现随着$W$的增大,区间$[L_i,R_i]$中满足$w_i \ge W$的矿石会随之减少,同样的,所有$v_i > 0$,因此 $Y_i$ 的值也会减少。

由于 $Y = \sum _iy_i$,所以$Y$随$W$单调递减。

因此我们可以二分出距离 $S$ 最近的值。

剩下的问题是当 $W$ 确定之后,我们如何快速求出每个 $Yi$。

这里可以预处理出所有满足 $w_i \ge W$ 的元素的前缀和,之后可以 $O(1)$ 时间求出每个区间中所有
$v_i$ 的和,以及满足要求的元素个数。

参考代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 2e5 + 10;

int n, m;
LL S;
int w[N], v[N];
int L[N], R[N];
int cnt[N];
LL sum[N];

LL get_y(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 + 10;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (get_y(mid) >= S) l = mid;
        else r = mid - 1;
    }

    printf("%lld\n", min(abs(get_y(r) - S), abs(S - get_y(r + 1))));

    return 0;
}

原题链接:[NOIP2011 提高组] 聪明的质监员

Q.E.D.