牛客网OJ题解--20210305

免费WiFi

https://ac.nowcoder.com/acm/problem/14707

本系列记录翀翀😐痛苦的刷题日志，所有题目均来自于牛客网OJ题目，坚持刷题谈起来容易做起来难，希望我可以坚持下去，这里仍然分享一段励志文案：每个人都有梦想，然而有些人把梦想变成了现实，有些人的梦想依旧是梦想，只因为他们为梦想付出的努力程度不一样，他们坚持的时间不一样，最终才有这样的结果。

NC14707-免费WIFI

题目链接

https://ac.nowcoder.com/acm/problem/14707

题目描述

TRDD开了一家免费WiFi体验店，所有人都可以免费连接WiFi，只有一个条件，你要提前一天预约。今天，TRDD收到了n(1 <= n <=1000)个人的预约，每个人有一个时间段[L, R] (1 <= L <= R <= 5000)表示这个人预约连接WiFi从L时刻到R时刻。但是市面上只有一种路由器，这种路由器单台最多能同时连接m(n <= 100)台设备， TRDD想要知道最少使用多少台路由器就能保证明天每个人都能连上WiFi。第一行包含两个数n(1 <= n <=1000), m (1 <= m <= 100)表示今天有n个人预约，以及路由单台最大连接个数m。
之后有n行，第i行有两个数字 [L, R] (1 <= L <= R <= 5000) 表示第i个人预约连接WiFi的时间是从L到R。输出一个数字表示TRDD最少需要开启的路由器的个数。

测试样例

输入

输出

解题思路

是一种典型的区间打表模拟，我们对于每一个是时间段都打印此时会有多少个人使用wifi，然后记录最大值，最大值就是所有时间段内人数峰值/m就好了。但是要注意当有余数时还需要再加一台机器。

解题代码

#include <bits/stdc++.h>
using namespace std;

//记录每一秒会有多少个人在用wifi
int a[5005];

int main()
{
    int n, m;
    cin >> n >> m;
    int Max = -1;
    while (n--)
    {
        int l, r;
        cin >> l >> r;
        //[l,r]区间的每一秒使用wifi的人数+1
        for (int i = l; i <= r; i++)
        {
            a[i]++;
            if (a[i] > Max)
            {
                //取每一时刻最大wifi位数
                Max = a[i];
            }
        }
    }
    int ans;
    //如果能整除，就是MAX/m
    if (Max % m == 0)
    {
        ans = Max / m;
    }
    else
    {
        //否则有余数要加一
        ans = Max / m + 1;
    }
    cout << ans << endl;
    system("pause");
    return 0;
}

luoguP1757-通天之分组背包

题目链接

https://www.luogu.com.cn/problem/P1757

题目描述

自 0101 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 0101 背包，他的物品大致可分为 k 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。两个数 m,n，表示一共有 n件物品，总重量为 m。

接下来 n 行，每行 33 个数 a_i,b_i,c_，表示物品的重量，利用价值，所属组数。请输出最大的价值。

测试样例

输入

输出

解题思路

就是九讲背包中的一个典型分组背包板子题，具体方法请食用本篇《浅谈三维0/1背包dp变式以及分组背包问题》。

解题代码

#include <bits/stdc++.h>
using namespace std;

//分别记录最大收益，物品重量，物品价值，物品所属组号
int dp[1005], w[1005], v[1005], g[1005];
using namespace std;
int main()
{
    int n, m;
    cin >> m >> n;
    int group = -1;
    for (int i = 1; i <= n; ++i)
    {
        cin >> w[i] >> v[i] >> g[i];
        group = max(group, g[i]);
    }
    //现规定本次所要打印的是第几组的物品
    for (int i = 1; i <= group; ++i)
    {
        //注意在分组背包中必须先讨论容量，再讨论物品，这是一个特殊顺序
        //可以保证每一个组只会选择一个物品
        //具体缘由见背包九讲
        //然后j逆序打印降维
        for (int j = m; j >= 0; --j)
        {
            //物品枚举范围正序
            for (int k = 1; k <= n; ++k)
            {
                //不是所要组号或者装不下跳过
                if (g[k] != i || j < w[k])
                    continue;
                //否则更新值
                dp[j] = max(dp[j], dp[j - w[k]] + v[k]);
            }
        }
    }
    cout << dp[m] << endl;
    system("pause");
    return 0;
}