滴滴笔试 - 0913

最佳速通时间

题面

小C准备参加某个游戏的速通比赛，为此他对该游戏速通了 $n$ 次，每次速通记录可以用一个数组 $A=\{a_1,a_2,……a_m\}$ 表示，其中 $a_i$ 表示小C从游戏开始到第 $i$ 个游戏节点所花赛的时间，$m$ 为游戏节点的个数。

请根据小C的速通记录计算出他的理论最佳速通时间，理论最佳速通时问指：小C在每两个相邻的游戏节点之间所花费的时间均达到了历史最佳记录，在此情况下所花费的总时间。

输入描述：
第一行两个正整数 $n,m$，表示有 $n$ 个速通记录，每个速通记录有 $m$ 个游戏节点。
接下来 $n$ 行，每行 $m$ 个正整数，第 $i$ 行的第 $j$ 个数 $a_{i,j}$ 表示在第 $i$ 次速通记录中，从游戏开始到第 $j$ 个游戏节点所花费的时间。
对于第 $i$ 行数据 $a_{i,1},a_{i,2},…,a_{i,m}$,满足 $0 < a_{i,1} < a_{i,2} < ... < a_{i,m}$
数据保证：$1≤n≤300,1≤m≤300,1≤a_{i,j}≤100 000 00$

输出描述：
一行一个整数，表示理论的最佳速通时间。

示例：

输入：3 5
      1 4 7 9 13
      2 3 8 11 14
      1 3 7 12 13
输出：8

思路与代码

初始化一个长度为 $m$ 的数组 $a$，用于存储每个游戏节点之间的最小时间差。初始值设为无穷大。

初始化变量 $s$ 用于累加理论最佳速通时间。 遍历每次速通记录：对于每次速通记录，遍历每个游戏节点。计算当前游戏节点与前一个游戏节点之间的时间差，并与 $a$ 数组中对应位置的值进行比较，取最小值。如果当前是最后一次速通记录，则将 $a$ 数组中的值累加到 $s$ 中。

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int main() {
    int m, n;
    cin >> m >> n;
    vector<int> a(n, INT_MAX);
    int s = 0;
    vector<vector<int>> nums(m, vector<int>(n));
    
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> nums[i][j];
        }
    }
    
    for (int i = 0; i < m; ++i) {
        int pre = 0;
        for (int j = 0; j < n; ++j) {
            int cur = nums[i][j];
            a[j] = min(a[j], cur - pre);
            pre = cur;
        }
    }
    
    for (int j = 0; j < n; ++j) {
        s += a[j];
    }
    
    cout << s << endl;

    return 0;
}

对比之美

题面

小美正在摆放她的收藏品。小美有一个漂亮的收藏架，有着一排 $n$个格子，从左到右分别编号为 $1, 2, … n$。小美打算把她的 $m$ 个收藏品放进这 $n$ 个格子之中，并且尽可能摆放地好看。

怎样才算好看呢？小美认为有对比才有美感，相邻两个格子收藏品数量之差越大就越美。形式化地讲，我们认为如果第 $i$ 个格子里摆放了 $a_i$ 个收藏品，那么美观度为 $\sum^{n}_{i=2}|a_i - a_{i - 1}|$。小美觉得有些格子不放藏品也可以接受，即要求 $a_i \ge 0, \sum^{n}_{i = 1}a_i = m$。请帮小美想出最美观的摆放方案！注意，$|x|$表示 $x$ 的绝对值，$|-5| = 5, |3| = 3$。

输入描述：
第一行一个整数 $T$ 表示数据组数。
对于每组数据：一行 $2$ 个整数分别为 $n$ 和$m$，表示格子数量和收藏品数量。
$1≤n,m≤1000000000,1≤T≤20$

输出描述：
输出一行 $T$ 个整数，表示最大的美观度，数字间有空格隔开。

示例：

输入：3
      1 50
      2 2
      3 1
输出：0 2 2
提示：对于第二组，摆放为 0 2 获得美观度 2；
      对于第三组，摆放为 0 1 0 获得美观度2。
      可以证明没有更优方案。

思路与代码

思维题。

显然题目把三种情况都告诉了：

• 只有一个格子，直接输出 $0$
• 两个格子，直接输出 $m$
• 大于两个格子的时候，直接输出 $2 × m$

#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;

    while (T--) {
        int n, m;
        cin >> n >> m;
        if (n == 1) {
            cout << 0 << " ";
        } else if (n == 2) {
            cout << m << " ";
        } else if (n > 2) {
            cout << 2 * m << " ";
        }
    }

    return 0;
}