刚刚牛客网举办了一场IT校招模拟考试，一共20道选择题，3道编程题，2个小时。

题目1

小牛牛为了向他的父母表现他已经长大独立了，他决定搬出去自己居住一段时间。
一个人生活增加了许多花费，牛牛每天必须吃一个水果并且需要每天支付 $x$ 元的房屋租金。
当前牛牛手中已经有 $f$ 个水果和 $d$ 元钱，牛牛也能去商店购买一些水果，商店每个水果售卖 $p$ 元。
牛牛为了表现他独立生活的能力，希望能独立生活的时间越长越好，牛牛希望你来帮他计算一下他最多能独立生活多少天。

输入描述

输入包括一行，四个整数 $x, f, d, p$ $(1 \le x, f, d, p \le 2 * 10^9)$，以空格分隔。

输出描述

输出一个整数，表示牛牛最多能独立生活多少天。

样例

输入：

3 5 100 10

输出：

11

算法

（数学公式）$O(1)$

首先判断一下是水果先用光，还是钱先用光：

• 如果是钱先用光，那独立生活的天数最多是 $\lfloor d / x \rfloor$；
• 如果水果先用光，那每天可以用多余的钱买水果，相当于每天的开销变成 $x + p$，那独立生活的天数最多是 $f + \lfloor (d - f * x) / (x + p)\rfloor$；

时间复杂度分析：仅有常数次计算，所以时间复杂度是 $O(1)$。

C++代码

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

using namespace std;

int main()
{
    int x, f, d, p;
    cin >> x >> f >> d >> p;
    if (f >= d / x) cout << d / x << endl;
    else
    {
        cout << f + (d - f * x) / (x + p) << endl;
    }
    return 0;
}

题目2

牛牛得知了一些股票今天买入的价格和明天卖出的价格，他找犇犇老师借了一笔钱，现在他想知道他最多能赚多少钱。

输入描述

每个输入包含一个测试用例。
输入的第一行包含两个正整数，表示股票的种数 $N (1 \le N \le 1000)$和牛牛借的钱$M (1 \le M \le 1000)$。
接下来 $N$ 行，每行包含两个正整数，表示这只股票每一股的买入价 $X (1 \le X \le 1000)$ 和卖出价 $Y (1 \le Y \le 2000)$。每只股票可以买入多股，但必须是整数。

输出描述：

输出一个整数表示牛牛最多能赚的钱数。

样例

输入：

3 5
3 6
2 3
1 1

输出：

4

算法

(背包问题) $O(NM)$

完全背包问题，相当于将 $N$ 种物品放入容量是 $M$ 的包中，每种物品的体积是买入价，价值是卖出价减去买入价，每种物品有无限多个。

时间复杂度分析：背包问题的时间复杂度是物品数量乘总容量，这道题目中物品数量是 $N$，背包总容积是 $M$，所以这道题目的时间复杂度是 $O(NM)$。

C++ 代码

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

using namespace std;

const int N = 1010;

int n, m;
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 0, x, y; i < n; i++)
    {
        cin >> x >> y;
        for (int j = x; j <= m; j++)
            f[j] = max(f[j], f[j - x] + y - x);
    }
    cout << f[m] << endl;
    return 0;
}

题目3

牛牛的快递到了，他迫不及待地想去取快递，但是天气太热了，以至于牛牛不想在烈日下多走一步。他找来了你，请你帮他规划一下，他最少走多少距离才能取回快递。

输入描述

每个输入包含一个测试用例。
输入的第一行包括四个正整数，表示位置个数 $N(2 \le N \le 10000)$，道路条数 $M(\le M \le 100000)$，起点位置编号 $S(1 \le S \le N)$ 和快递位置编号 $T (1 \le T \le N)$。位置编号从 1 到 $N$，道路是单向的。数据保证 $S \ne T$，保证至少存在一个方案可以从起点位置出发到达快递位置再返回起点位置。
接下来 $M$ 行，每行三个正整数，表示当前道路的起点位置编号 $U (1 \le U \le N)$ 和终点位置编号 $V(1 \le V \le N)$，以及当前道路的长度 $D(1 \le D \le 1000)$。

输出描述

对于每个用例，在单独的一行中输出从起点出发抵达快递位置再返回起点的最短距离。

样例

输入：

3 3 1 3
1 2 3
2 3 3
3 1 1

输出：

7

算法

（最短路，spfa）$O(km)$

最短路问题。先求一遍从起点 $S$ 到终点 $T$ 的最短路，再求一遍从终点 $T$ 到起点 $S$ 的最短路，答案就是两个最短距离的和。

常用的最短路算法有dijkstra和spfa，二者区别如下：

• dijkstra只能处理边权都是正数的情况，朴素dijkstra的时间复杂度是$O(n^2+m)$，用二叉堆优化的时间复杂度是$O((n+m)logn)$，用fibonacci堆优化的时间复杂度是$O(nlogn + m)$；
• spfa是bellman-ford算法的改进版，可以处理边是负权的情况，时间复杂度平均情况下是 $O(km)$，其中 $k$ 是常数，最坏情况下时间复杂度是 $O(nm)$，但实际应用中一般不会遇到最坏情况（网格图可能会比较慢）；

一般情况下，spfa的运行效率要高于dijkstra，而且代码更简洁一点，所以这道题目采用了spfa算法。

时间复杂度分析：spfa平均运行时间 $O(km)$，其中 $k$ 是常数，$m$ 是边的数量。

C++ 代码

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

using namespace std;

const int N = 10010, M = 100010, INF = 1000000000;

int n, m, S, T;
int h[N], v[M], e[M], ne[M], idx;
int d[N], q[N];
bool st[N];

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

int spfa()
{
    int hh = 0, tt = 1;
    q[0] = S;
    for (int i = 1; i <= n; i++) d[i] = INF;
    d[S] = 0, st[S] = 1;

    while (hh != tt)
    {
        int t = q[hh++];
        st[t] = 0;
        if (hh == N) hh = 0;
        for (int i = h[t]; i != -1; i = ne[i])
            if (d[e[i]] > d[t] + v[i])
            {
                d[e[i]] = d[t] + v[i];
                if (!st[e[i]])
                {
                    q[tt++] = e[i];
                    st[e[i]] = 1;
                    if (tt == N) tt = 0;
                }
            }
    }
    return d[T];
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m >> S >> T;
    for (int i = 0, x, y, z; i < m; i++)
    {
        cin >> x >> y >> z;
        add(x, y, z);
    }

    int res = spfa();
    swap(S, T);
    res += spfa();
    cout << res << endl;
    return 0;
}