2019牛客暑期NOIP真题班提高组2-二分

1. 关押罪犯

来源：NOIP2003提高组 https://ac.nowcoder.com/acm/contest/258/C

算法知识点：二分，染色法判断二分图

复杂度： $O((N + M)logC)$

解题思路：

将罪犯当做点，罪犯之间的仇恨关系当做点与点之间的无向边，边的权重是罪犯之间的仇恨值。
那么原问题变成：将所有点分成两组，使得各组内边的权重的最大值尽可能小。

我们在 $[0, 10^9]$ 之间枚举最大边权 $limit$ ，当 $limit$ 固定之后，剩下的问题就是：

判断能否将所有点分成两组，使得所有权值大于 $limit$ 的边都在组间，而不在组内。也就是判断由所有点以及所有权值大于 $limit$ 的边构成的新图是否是二分图。

判断二分图可以用染色法，时间复杂度是 $O(N + M)$ ，其中 $N$ 是点数， $M$ 是边数。

为了加速算法，我们来考虑是否可以用二分枚举 $limit$ ，假定最终最大边权的最小值是 $Ans$ :

那么当 $limit \in [ans, 10^9]$ 时，所有边权大于 $limit$ 的边，必然是所有边权大于 $Ans$ 的边的子集，因此由此构成的新图也是二分图。
当 $limit \in [0, ans - 1]$ 时，由于 $ans$ 是新图可以构成二分图的最小值，因此由大于 $limit$ 的边构成的新图一定不是二分图。
所以整个区间具有二段性，可以二分出分界点 $ans$ 的值。

时间复杂度分析

总共二分 $logC$ 次，其中 $C$ 是边权的最大值，每次二分使用染色法判断二分图，时间复杂度是 $O(N + M)$ ，其中 $N$ 是点数， $M$ 是边数。因此总时间复杂度是 $O((N + M)logC)$ 。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 20010,
    M = 200010;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int color[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool dfs(int u, int c, int limit)
{
    color[u] = c;
    for (int i = h[u]; ~i; i = ne[i])
    {
        if (w[i] <= limit) continue;
        int j = e[i];
        if (color[j])
        {
            if (color[j] == c) return false;
        }
        else if (!dfs(j, 3 - c, limit)) return false;
    }

    return true;
}

bool check(int limit)
{
    memset(color, 0, sizeof color);

    for (int i = 1; i <= n; i++)
        if (color[i] == 0)
            if (!dfs(i, 1, limit))
                return false;
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }

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

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

2. 聪明的质检员

来源：NOIP2011提高组 https://ac.nowcoder.com/acm/contest/259/B

算法知识点：二分，前缀和

复杂度： $O(n^2)$

解题思路：

观察每个区间的值 $Y\_i = (\sum \_j 1) * (\sum \_j v\_j), j \in [L\_i, R\_i] 且 w\_j \ge W$ 。

当 $W$ 增大时，区间 $[L\_i, R\_i]$ 中满足要求的 $(w\_i, v\_i)$ 会减少，同时所有 $v\_i \ge 0$ ，因此 $Y\_i$ 的值也会减少。

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

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

剩下的问题是当 $W$ 确定之后，我们如何快速求出每个 $Y\_i$ 。
这里可以预处理出所有满足 $w\_i \ge W$ 的元素的前缀和，之后可以 $O(1)$ 时间求出每个区间中所有 $v\_i$ 的和，以及满足要求的元素个数。

时间复杂度分析：

总共二分 $O(logW)$ 次，每次预处理前缀和的计算量是 $O(N)$ ，求 $Y$ 的计算量是 $O(M)$ 。因此总时间复杂度是 $O(N + M)logW)$ 。

C++ 代码：

#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;
}

3. 借教室

来源：NOIP2012提高组 https://ac.nowcoder.com/acm/contest/260/B

算法知识点：二分，差分

复杂度： $O((n + m)logm$

解题思路：

由于随着订单数量的增加，每天可用教室的数量一定单调下降。
因此我们可以二分出第一天出现负值的订单编号。

剩下的问题是如何快速求出经过若干订单后，每天所剩的教室数量。
每个订单的操作是 $[L\_i, R\_i]$ 全部减去 $d\_i$ 。

因此我们可以用差分来加速处理过程。

时间复杂度分析：

总共二分 $O(logm)$ 次，其中 $m$ 是订单数量。每次二分后使用差分求出每天最终教室数量，计算量是 $O(n + m)$ ，因此总时间复杂度是 $O(n + m)logm)$ 。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL; const int N = 1000010;

int n, m;
int r[N], d[N], s[N], t[N];
LL b[N];

bool check(int k)
{
    for (int i = 1; i <= n; i++) b[i] = r[i];

    for (int i = 1; i <= k; i++)
    {
        b[s[i]] -= d[i];
        b[t[i] + 1] += d[i];
    }

    LL res = 0;
    for (int i = 1; i <= n; i++)
    {
        res += b[i];
        if (res < 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 = n; i; i--) r[i] -= r[i - 1];

    for (int i = 1; i <= m; i++) scanf("%d%d%d", &d[i], &s[i], &t[i]);

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

    if (check(r))
    {
        puts("-1");
        printf("%d\n", r);
    }
    else puts("0");

    return 0;
}

4. 跳石头

来源：NOIP2015提高组 https://ac.nowcoder.com/acm/contest/263/A

算法知识点：二分，贪心

复杂度： $O(NlogL)$

解题思路：

如果长度 $Len$ 可以满足，那么当长度小于 $Len$ 时也可以满足，所以我们可以二分出最大的 $Len$ 。

剩下的问题是如何判断给定 $Len$ 的情况下，能否最多拿走 $M$ 块石头，使得所有相邻两块石头之间的距离不小于 $Len$ 。

这一步可以贪心来做。从前往后扫描，并记一下上一块石头的位置。

如果当前石头和上一块石头的距离小于 $Len$ ，则将当前石头拿走。这里给出证明：如果某个最优解中是拿走了上一块石头，那么我们可以改成留下上一块石头，拿走当前这块石头，这样总共拿走的石头数量不变，所以当前选法也是一组最优解。
如果当前石头和上一块石头的距离大于等于 $Len$ ，则将上一块石头更新成当前这块。

扫描结束后判断拿走的石头数量是否小于等于 $M$ 。

时间复杂度分析:

总共二分 $O(logL)$ 次，每次贪心的计算是 $O(N)$ ，因此总时间复杂度是 $O(NlogL)$ 。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 50010;

int L, n, m;
int d[N];

bool check(int mid)
{
    int last = 0, cnt = 0;
    for (int i = 1; i <= n; i++)
        if (d[i] - last < mid) cnt++;
        else last = d[i];
    return cnt <= m;
}

int main()
{
    scanf("%d%d%d", &L, &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &d[i]);
    d[++n] = L;

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

    printf("%d\n", r);
    return 0;
}

另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ