场景题

题一：最高得分

一个长度为 $N$ 的序列，玩家每次只能从头部或尾部拿数字，不能从中间拿。拿走的数字依次从左到右排列在自己面前。拿完 $N$ 个数字之后，游戏结束。此时 $N$ 个数字在玩家面前组成一个新的排列，这个数列每相邻两个数字之差的绝对值之和为玩家最终得分。假设玩家前面的 $N$ 个数字从左到右标号为 $n_{1}, n_{2}, \dots, n_{N}$ ，则最终得分 $S$ 的计算方式如下：

S = abs (n_{1} - n_{2}) + abs (n_{2} - n_{3}) + \dots + abs (n_{N - 1} - n_{N}) .

请计算玩家在以上游戏规则中把所有数字拿完可以获得的最大得分。

思路：拿到这个问题，感觉像是动态规划。得想办法把子问题拆出来。但是一般情况下，并不是这么好拆的。所以从最简单的用例开始。假设只有两个数，这很简单，无论怎么拿，得分都一样。再加一个数呢？你就要考虑从哪里先拿，然后再从哪里先拿的问题。假设现在有三个数，你从前端拿了一个数，则下一步你得考虑从哪里拿的增益比较大。从前端拿得到一个front_gain, 从末端拿得到一个back_gain. 你得比一比哪个会让你的得分最大化。然后下一步继续这样考虑，这就形成了一个递归步。就是说你已经拆出来了！专业店说就是你找除了递推关系式。题外话：Case analysis is more powerful than you thought!

#include<iostream>
#include<vector>
#include<cmath>
 
using namespace std;
 
/**
 * @breif Calculate the max score of the given array.
 * @param arr     The origin array.
 * @param beg     The begining of the range.
 * @param end     The end of the range.
 * @param isFront Is the last taken from the front or not.
 * @return        The max score in a paticular setting.
 *
 * Note that the @c arr is the origin array, and [beg, end)
 * range is considered from the second step, with @c isFront.
 * For example:
 *   Suppose @c arr.size() = 5
 *   If @c isFront = true, means the last taken is from the front,
 *   then [beg, end) = [1, 5).
 *   If @c isFront = false, means the last taken is from the back,
 *   then [beg, end) = [0, 4).
 */
int opt(const vector<int>& arr, int beg, int end, bool isFront) {
    // base cases
    if (beg >= end) return 0;
    if (end - beg == 1) {
        if (isFront)
            return abs(arr[beg] - arr[beg-1]);
        else
            return abs(arr[beg] - arr[end]);
    }
 
    // ELSE
    int front_gain = 0; // the gain if take front at current step
    int back_gain = 0;  // the gain if take back at current step
    
    if (isFront)
    {
        front_gain = abs(arr[beg] - arr[beg-1]);
        back_gain = abs(arr[end-1] - arr[beg-1]);
    }
    else
    {
        front_gain = abs(arr[beg] - arr[end]);
        back_gain = abs(arr[end-1] - arr[end]);
    }
    return max(
            front_gain + opt(arr, beg+1, end, true),
            back_gain + opt(arr, beg, end-1, false));
}
 
 
int main()
{
    int N = 0;
    cin >> N;
    vector<int> arr;
    for (int i=0; i!=N; ++i)
    {
        int tmp;
        cin >> tmp;
        arr.push_back(tmp);
    }
 
    int maxwin = max(
            opt(arr, 1, arr.size(), true),
            opt(arr, 0, arr.size()-1, false));
    cout << maxwin;
 
    return 0;
}

题二：最少硬币

2019腾讯实习生笔试题

小Q去商场购物，经常会遇到找零钱的问题。小Q现在手上有 $n$ 种不同面值的硬币，每种面值的硬币有无限多个。为了方便购物，小Q希望带尽量少的硬币，并且要能组合出 $1$ 到 $m$ 之间（包含 $1$ 和 $m$ ）的所有面值。

输入描述：第一行包含两个整数 $m, n (1 \leq n \leq 100, 1 \leq m \leq 1 0^{9})$ ，含义如题所述。接下来 $n$ 行，每行一个整数，每 $i + 1$ 行的整数表示第 $i$ 种硬币的面值。

输出描述：输出一个整数，表示最少需要携带的硬币数量。如果无解，则输出 $- 1$ .

示例输入：

示例输出：

思路：一拿到就让人联想到动态规划。但其实不是，因为它的条件是要构成所有1到m之间的面值。所以就得从1到m慢慢凑出来。假设当前选择的硬币已经可以构成[1, i], 那么我当然下次在选面值的之后，会很理想的去寻找一个面值为i+1的硬币。这样我可以使我构造的最大面值尽可能的大。如果这个面值大于m了，那我们就完事儿了。这是贪心的思想。具体来说，比方已选的硬币可以构造出1到5之间的任何面值，那我在选择一个面值为6的硬币，就可以构造出1到11之间的任何面值。所以我们从面值为1的开始加，记录当前可以构造的最大面值max_constructed，在选择下一个硬币的时候，优先选择面值⇐max_constructed+1的硬币。参考：https://blog.csdn.net/MOU_IT/article/details/89057036

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int MinimalCoin(const vector<int>& coins, int amount)
{
  if (coins.empty())
    throw std::invalid_argument("empty coins");
  if (coins[0] != 1)
    return -1;
 
  int max_constructed = 0;
  int cnt = 0;
  do
  {
    for (int n = coins.size() - 1; n >= 0; --n)
    {
      if (coins[n] <= max_constructed + 1)
      {
        max_constructed += coins[n];
        ++cnt;
        break;
      }
    }
    
  } while (max_constructed < amount);
 
  return cnt;
}
 
int main()
{
  // address input
  int n, m;
  cin >> m >> n;
 
  int val;
  vector<int> coins;
  for (int i = 0; i != n; ++i)
  {
    cin >> val;
    coins.push_back(val); 
  }
 
  std::sort(coins.begin(), coins.end());
  cout << MinimalCoin(coins, m);
 
  return 0;
}

题四：舞会

链接：https://www.nowcoder.com/questionTerminal/9efe02ab547d4a9995fc87a746d7eaec 来源：牛客网

今天，在冬木市举行了一场盛大的舞会。参加舞会的有n 位男士，从 1 到 n 编号；有 m 位女士，从 1 到 m 编号。对于每一位男士，他们心中都有各自心仪的一些女士，在这次舞会中，他们希望能与每一位自己心仪的女士跳一次舞。同样的，对于每一位女士，她们心中也有各自心仪的一些男士，她们也希望能与每一位自己心仪的男士跳一次舞。在舞会中，对于每一首舞曲，你可以选择一些男士和女士出来跳舞。但是显然的，一首舞曲中一位男士只能和一位女士跳舞，一位女士也只能和一位男士跳舞。由于舞会的时间有限，现在你想知道你最少需要准备多少首舞曲，才能使所有人的心愿都得到满足？

input: 第一行包含两个整数n,m，表示男士和女士的人数。1≤n,m≤ 1000 接下来n行，第i行表示编号为i的男士有ki个心仪的女生然后包含ki个不同的整数分别表示他心仪的女士的编号。接下来m行，以相同的格式描述每一位女士心仪的男士。

output: 一个整数，表示最少需要准备的舞曲数目。

示例输入：

示例输出：

说明：

对于样例2，我们只需要两首舞曲，第一首舞曲安排（1,1），（2,3），（3,2）；第二首舞曲安排（1,2），(2,1)，（3,3）。

思路：乍一看好象很难，不知道怎么处理。其实只要仔细看清楚题目要求：要求每个刃都能得到满足！这很重要，即便还有一个我喜欢的人没跟我跳，就得再放一首歌让我跳！了解到这个需求之后，问题就变的简单了，只要统计出每个人心仪人的数量，以及被心仪的数量，对所有人求一个最大值就行了。参考：https://www.nowcoder.com/questionTerminal/9efe02ab547d4a9995fc87a746d7eaec

#include <iostream>
#include <vector>
 
using std::vector;
 
int main()
{
  // read input and built heartbeat matrix
  int num_men, num_women, num_likes, val;
  std::cin >> num_men >> num_women;
  int total_num = num_men + num_women;
  // the heartbeat matrix
  vector<vector<int> > mat(total_num, vector<int>(total_num, 0));
 
  for (int i = 0; i != total_num; ++i)
  {
    std::cin >> num_likes;
    while (num_likes--)
    {
      std::cin >> val;
      if (i < num_men)  // man to woman
        mat[i][val+num_men-1] = 1;
      else // woman to man
        mat[i][val-1] = 1;
    }
  }
  // done
  
  // count for each persons hearbeats
  int songs_needed = 0;
  for (int i = 0; i != total_num; ++i)
  {
    int cnt = 0;
    if (i < num_men)  // counting for each man
    {
      for (int j = num_men; j != total_num; ++j)
      {
        if (mat[i][j] == 1) // man i like woman j
          ++cnt;
        else if (mat[j][i] == 1) // man i is liked by woman j
          ++cnt;
      }
    }
    else
    {
      for (int j = 0; j != num_men; ++j)
      {
        if (mat[i][j] == 1)
          ++cnt;
        else if (mat[j][i] == 1)
          ++cnt;
      }
    }
    if (songs_needed < cnt) songs_needed = cnt; // update songs if needed
  }
  
  std::cout << songs_needed;
  return 0;
}

题八：点击窗口的索引

网易雷火游戏2019校招

本题需要让你模拟一下在Windows系统里窗口和鼠标的点击操作，具体如下：

屏幕分辨率为3840x2160，左上角坐标为(0, 0)，右下角坐标为(3839, 2159).
窗口是一个矩形的形状，由左上角坐标(x, y), 和宽高(w, h)四给数字来定位。左上角坐标为(x, y), 右下角坐标为(x+w, y+h). 其中左上角坐标一定会在屏幕范围内，其他一些部分可能会超过屏幕范围。
窗口的点击和遮挡规则同Windows，但是不考虑关闭窗口、最大化、最小化和强制置顶的情况。即，
如果发生重叠，后面打开的窗口会显示在前面打开的窗口上面
当鼠标发生一次点击的时候，需要判断点击到了哪个窗口，如果同个坐标有多个窗口，算点击到最上层的那个
当一个窗口被点击的时候，会浮动到最上层

输入描述：每个测试输入包含1个测试用例。第一行为2个整数N，M。其中N表示打开窗口的数目，M表示鼠标点击的数目，其中 $0 < N, M < 1000$ . 接下来N行，每一行四个整数 $x_{i}, y_{i}, w_{i}, h_{i}$ , 分别表示第i个窗口（窗口id为i，从1开始计数）的左上角坐标以及宽高，初始时窗口是按输入的顺序依次打开。其中 $0 \leq x_{i} < 3840$ , $0 \leq y_{i} < 2160$ , $0 < w_{i} < 3840$ , $0 < h_{i} < 2160$ . 再接下来有M行，每一行两个整数 $x_{j}, y_{j}$ , 分别表示接下来发生的鼠标点击坐标。其中 $0 \leq x_{j} < 3840, 0 \leq y_{j} < 2160$

输出描述：对于每次鼠标点击，输出本次点击到的窗口id。如果没有点击到窗口，输出-1.

示例输入：

2 4
100 100 100 100
10 10 150 150
105 105
180 180
105 105
1 1

示例输出：

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
// global const
enum {
  WIDTH = 3840,
  HEIGHT = 2160
};
 
// abstraction for 2D point
struct Pos
{
  int x;
  int y;
  Pos(int xx, int yy): x(xx), y(yy)
  {
  }
};
 
// abstraction for window
struct Window
{
  int id;
  Pos point;
  int width;
  int height;
  Window(int idx, int x, int y, int w, int h)
    : id(idx), point(x, y), width(w), height(h)
  {
  }
};
 
/// is the point @c p in the window @c w
bool IsInWindow(const Window& w, const Pos& p)
{
  int left = w.point.x;
  int right = 
    (left + w.width < WIDTH) ? (left + w.width) : WIDTH-1;
  int top = w.point.y;
  int bot = 
    (top + w.height < HEIGHT) ? (top + w.height) : HEIGHT-1;
 
  if (p.x >= left && p.x <= right)
  {
    if (p.y >= top && p.y <= bot)
      return true;
  }
  return false;
}
 
///  which window do i click on
int ClickWhich(vector<Window>& windows, const Pos& click)
{
  // 窗口叠放次序，从上层到下层
  for (int i = windows.size() - 1; i >= 0; --i)
  {
    if (IsInWindow(windows[i], click))
    {
      int ret = windows[i].id + 1;
      windows.push_back(windows[i]);
      windows.erase(windows.begin() + i);
      return ret;
    }
  }
  return -1;
}
 
int main()
{
  int num_open_windows, num_clicks;
  cin >> num_open_windows >> num_clicks;
  // read windows
  vector<Window> windows;
  for (int i = 0, x,y,w,h; i != num_open_windows; ++i)
  {
    cin >> x >> y >> w >> h;
    windows.emplace_back(i, x, y, w, h);
  }
  // read clicks
  vector<Pos> clicks;
  for (int i = 0, x,y; i != num_clicks; ++i)
  {
    cin >> x >> y;
    clicks.emplace_back(x, y);
  }
  // io done
  
  for (auto &e : clicks)
  {
    cout << ClickWhich(windows, e) << endl;  
  }
 
  return 0;
}

树相关

Josephus Problem

这个问题是以弗拉维奥·约瑟夫命名的，他是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。

——维基百科

描述：人们站在一个等待被处决的圈子里。计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。在跳过指定数量的人之后，执行下一个人。对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放。（牛客网上类似的题[^c]）

问题即，给定人数、起点、方向和要跳过的数字，选择初始圆圈中的位置以避免被处决。

解法：维基百科[^a]上也有，GeeksforGeeks[^b]还有视频教程。

常见的有两种解法：

单链表模拟
数学递推

显然，假设n个人编号： $0, 1, 2, 3, \dots, n - 1$ . 从0号开始报数（报数从0开始），报到m-1的将被处决，然后从下一个人开始报数。直到剩下最后一个人，赦免之。

第一趟：报到 m 的自然是编号为 $(m - 1) mod n$ . 接着从 $m mod n$ 开始报数，接下来又会是谁被处决呢？

等等，先来看看问题是什么，我希望知道幸免者的编号。在n个人，报m个数的设定下，我希望知道幸免者编号，假设这个编号就是 $f (n, m)$ , 这里 $f$ 是个神奇的函数，我只要告诉它 n 和 m 它就能告诉我最后幸存者的编号。如果我能找到 $f (n, m)$ 和 $f (n - 1, m)$ 的递推关系式，那将是极好的。

在第一趟之后，报数从编号 $k = m mod n$ 开始，但是此时只有 n-1个人，我还是想知道幸存者的编号。如果此时将编号重新映射一下，比如：

k   -> 0
k+1 -> 1
...
k-2 -> n-2

那么问题就变成了 n-1 个人，从0开始报数，报到 m-1 被处决，完完全全成了一个拥有同样结构的问题，但是规模更小了。显然，这个问题的解是 $f (n - 1, m)$ . 但是呢，我们得到的编号却不是原来的编号了，得把编号还原回去。这很简单，假设得到的编号是 x，那么映射回原编号 y

y = (x+k) mod n

于是，如果我们能够知道 $f (n - 1, m)$ , 那么

f (n, m) = (f (n - 1, m) + m) mod n .

这就得到了递推公式，接着看一下边界条件，当n = 1时， $f (1, m) = 0$ ; 结束。

int Josephus(int n, int m)
{
  if (n < 1)
    throw std::invalid_argument("we need n >= 1");
  if (n == 1)
    return 0;
  return (Josephus(n-1, m) + m) % n;
}

出列的顺序（类约瑟夫环）

VIVO 2020校招正式批

将N个人排成一排，从第一个人开始报数，如果报数是M的倍数就出列，报道队尾后则回到队头继续报数，直到所有人都出列。

输入描述：输入2个正整数，空格分隔，第一个代表人数N，第二个代表M。

输出描述：输出一个数组，每个数据表示原来在队列中的位置，用空格隔开，表示出列顺序

输入实例：

6 3

输出示例：

3 6 4 2 5 1

说明：6个人排成一排，原始位置编号1-6，最终输出为3 6 4 2 5 1，
表示的是原来编号为3的第一个出列，编号为1的最后出列。

思路：类似于约瑟夫环，使用链表模拟整个过程即可。

#include <iostream>
#include <vector>
 
using namespace std;
 
struct Node
{
  int val;
  Node* next;
  Node(int n): val(n), next(nullptr) {}
};
 
vector<int> ToQueue(int num_employee, int mod)
{
  if (num_employee == 0) return vector<int>();
  if (num_employee == 1) return vector<int>(1, 1);
  // else num_employee >= 2
  
  // build list
  vector<Node*> nodes;
  for (int i = 1; i <= num_employee; ++i)
  {
    Node* p = new Node(i);
    nodes.push_back(p);
  }
  for (size_t i = 1; i != nodes.size(); ++i)
  {
    nodes[i-1]->next = nodes[i];
  }
  nodes.back()->next = nodes.front();
 
  Node* prev = nodes.back();
  Node* cur = nodes.front();
  vector<int> ret;
  for (int count = 1; cur->next != cur; ++count)
  {
    if (count % mod == 0)
    {
      ret.push_back(cur->val);
      prev->next = cur->next;
      cur = cur->next;
    }
    else
    {
      prev = cur;
      cur = cur->next;
    }
  }
  ret.push_back(cur->val);
  // memory clean
  for (Node* p : nodes) delete p;
  return ret;
}
 
int main()
{
  int num_employee, mod;
  cin >> num_employee >> mod;
  for (auto e : ToQueue(num_employee, mod))
    cout << e << " ";
  return 0;
}

最短通行时间

度小满金融2020校招

有N辆车要陆续通过一座最大承重为W的桥，其中第i辆车的重量为w[i], 过桥时间为t[i]. 要求：第辆车上桥时间不早于第i-1辆车上桥的时间；i任意时刻桥上所有车辆的总重量不超过W。那么，所有车辆都通过这座桥的所需的最短时间是多少？

输入：

第一行输入两个整数N，W（1 <= N, W <= 100000）
第二行输入N个整数w[1]到w[N]（1 <= w[i] <= W）
第三行输入N个整数t[1]到t[N]（1 <= t[i] <= 10000）

4 2
1 1 1 1
2 1 2 2

输出：

干就完了，模拟！

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int MinTime(const vector<int>& car_weights,
            vector<int>& pass_times,
            const int max_weight)
{
  int len = car_weights.size();
  int elapsed_time = 0;
  int cur = 0;
  int w = max_weight;
 
  for (;;)
  {
    int start = cur;
    while (cur < len && w >= car_weights[cur])
    {
      w -= car_weights[cur++];
    }
 
    if (cur >= len) // reach the last car
    {
      elapsed_time += 
        *std::max_element(pass_times.begin() + start, pass_times.end());
      return elapsed_time;
    }
    else
    {
      // each time a car passed, some other car may board the bridge
      int mintime_idx = 0;
      for (int i = 0; i < cur; ++i)
      {
        if (pass_times[mintime_idx] > pass_times[i] && pass_times[i] != 0)
          mintime_idx = i;
      }
      elapsed_time += pass_times[mintime_idx];
 
      for (int i = 0; i < cur; ++i) // update time
        pass_times[i] = max(pass_times[i] - pass_times[mintime_idx], 0);
 
      // car @mintime_idx has passed, now @w may be free to pass a new car
      w += car_weights[mintime_idx];
    }
  }
}
 
int main()
{
  int num_car, max_weight;
  cin >> num_car >> max_weight;
  vector<int> car_weights;
  for (int n = num_car, w; n--;)
  {
    cin >> w;
    car_weights.push_back(w);
  }
  vector<int> pass_times;
  for (int n = num_car, t; n--;)
  {
    cin >> t;
    pass_times.push_back(t);
  }
  // io done
  cout << MinTime(car_weights, pass_times, max_weight);
  return 0;
}

经过棋盘的最小开销

58同城2020校招

现有一个地图，由横线与竖线组成（参考围棋棋盘），起点在左上角，终点在右下角。每次行走只能沿线移动到相邻的点，每走一步产生一个开销。计算从起点到终点的最小开销为多少。

输入描述： $m \times n$ 的地图表示如下

3
3
1 3 4
2 1 2
4 3 1

其中m=3，n=3表示3*3的矩阵
行走路径为：下>右>右>下

输出描述：

路径总长：1+2+1+2+1=7

动态规划入门题，可惜我当时碰到DP就慌，而且只会递归DP，自顶向下，复杂度会高很多。

假设用一个矩阵，名字就叫dp，表示最优结果。dp(i,j)表示从起点到坐标(i,j)的最小开销。很容易得到递推关系：

dp (i, j) = ⎩ ⎨ ⎧ map (i, j) + min (dp (i, j - 1), dp (i - 1, j)) \sum_x = 0^{j - 1} map (i, j) \sum_x = 1^{i - 1} map (i, j) i, j > 0 i = 0 j = 0 .

#include <iostream>
#include <vector>
 
using namespace std;
 
// greedy
int MinCost(const vector<vector<int>>& mat)
{
  int row = static_cast<int>(mat.size());
  int col = static_cast<int>(mat[0].size());
  int i = 0;
  int j = 0;
  int ret = 0;
  while (i < row-1 && j < col-1)
  {
    ret += mat[i][j];
    if (mat[i+1][j] < mat[i][j+1]) ++i;
    else ++j;
  }
  if (i == row-1)
  {
    for (int x = j; x <= col-1; ++x)
      ret += mat[i][x];
  }
  else
  {
    for (int x = i; x <= row-1; ++x)
      ret += mat[x][j];
  }
  return ret;
}
 
// dynamic programming
int mincost(const vector<vector<int>>& mat)
{
  int row = static_cast<int>(mat.size());
  int col = static_cast<int>(mat[0].size());
  vector<vector<int>> dp(row, vector<int>(col, 0));
  // initialize
  dp[0][0] = mat[0][0];
  for (int i = 1; i < row; ++i)
    dp[i][0] = dp[i-1][0] + mat[i][0];
  for (int j = 1; j < col; ++j)
    dp[0][j] = dp[0][j-1] + mat[0][j];
 
  for (int i = 1; i < row; ++i)
  {
    for (int j = 1; j < col; ++j)
    {
      dp[i][j] = mat[i][j] + min(dp[i-1][j], dp[i][j-1]);
    }
  }
  return dp[row-1][col-1];
}
 
int main()
{
  int num_rows, num_cols;
  cin >> num_rows >> num_cols;
  vector<vector<int>> mat(num_rows, vector<int>(num_cols, 0));
  for (int i = 0; i != num_rows; ++i)
  {
    for (int j = 0, x; j != num_cols; ++j)
    {
      cin >> x;
      mat[i][j] = x;
    }
  }
  // io done
  cout << mincost(mat);
  return 0;
}

Learn2Live

探索

场景题

场景题

题一：最高得分

题二：最少硬币

题四：舞会

题八：点击窗口的索引

Josephus Problem

出列的顺序（类约瑟夫环）

最短通行时间

经过棋盘的最小开销

关系图谱

目录

反向链接