Oj.Nbdp.Net  初赛题库  问题  状态  排名  团队  题解  课程 题目描述 感应门会在有人经过的时候自动打开，等待 x 秒后自动关闭。如果在门打开的时候有人通过，那么等待时间会被重置，重新计算 x 秒后再关闭。 给定一段时间内通过感应门的记录，请计算感应门一共开放了多少时间。 输入 第一行：两个正整数 n 与 x ， n 表示通过感应门的人数， x 表示感应门的等待时间。 第二行： n 个正整数 t 1 , t 2 ,⋯, t n ，每个数字表达一个人通过感应门的时刻。 输出 样例输入输出 输入#1 复制 7 3 1 2 7 10 15 17 22 输出#1 复制 18 提示 对于 50% 的数据， 1≤n≤1000 ； 对于 100% 的数据， 1≤n≤ 10 5 ， 1≤ t i ≤ 10 9 ，且 t 1 ≤ t 2 ≤ t 3 ≤⋯≤ t n 。c++代码

以下是 C++ 代码实现：

#include <iostream>
using namespace std;

int main() {
    int n, x;
    cin >> n >> x;

    int last_time = 0; // 上一个通过感应门的时刻
    int total_time = 0; // 感应门开放的总时间

    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        if (t - last_time > x) { // 如果感应门已经关闭
            total_time += x; // 记录感应门开放的时间
        } else { // 如果感应门还未关闭
            total_time += t - last_time; // 记录感应门开放的时间
        }
        last_time = t; // 更新上一个通过感应门的时刻
    }

    total_time += x; // 最后一次通过感应门后，感应门还会开放 x 秒
    cout << total_time << endl;

    return 0;
}

相关问题

Oj.Nbdp.Net  初赛题库  问题  状态  排名  团队  题解  课程 题目描述 感应门会在有人经过的时候自动打开，等待 x 秒后自动关闭。如果在门打开的时候有人通过，那么等待时间会被重置，重新计算 x 秒后再关闭。 给定一段时间内通过感应门的记录，请计算感应门一共开放了多少时间。 输入 第一行：两个正整数 n 与 x ， n 表示通过感应门的人数， x 表示感应门的等待时间。 第二行： n 个正整数 t 1 , t 2 ,⋯, t n ，每个数字表达一个人通过感应门的时刻。 输出 样例输入输出 输入#1 复制 7 3 1 2 7 10 15 17 22 输出#1 复制 18 提示 对于 50% 的数据， 1≤n≤1000 ； 对于 100% 的数据， 1≤n≤ 10 5 ， 1≤ t i ≤ 10 9 ，且 t 1 ≤ t 2 ≤ t 3 ≤⋯≤ t n 。思路

题目描述：

有一道门，门在有人经过的时候会自动打开，等待 x 秒后自动关闭。如果在门打开的时候有人通过，那么等待时间会被重置，重新计算 x 秒后再关闭。 现在给定一段时间内通过感应门的记录，请计算感应门一共开放了多少时间。

输入：

第一行：两个正整数 n 与 x ，n 表示通过感应门的人数，x 表示感应门的等待时间。

第二行：n 个正整数 t1,t2,⋯,tn，每个数字表达一个人通过感应门的时刻。

输出：

输出感应门一共开放的时间。

思路：

先设置两个变量，一个是门的状态变量 is_open，另一个是门的开放时长变量 open_time，将两个变量均初始化为 0。然后遍历通过感应门的记录，对于每个记录：

如果门是关闭的，将门的状态变量 is_open 设为 1，并将门的开放时长变量 open_time 加上感应门的等待时间 x。

如果门是开着的，将门的开放时长变量 open_time 加上感应门的等待时间 x 减去当前人通过感应门的时间与上一个人通过感应门的时间的差值。

最后输出门的开放时长变量 open_time 即可。

时间复杂度：O(n)

完整代码实现如下：

Oj.Nbdp.Net  初赛题库  问题  状态  排名  团队  题解  课程 问题 D: 直线运输  题目  状态  题解 题目描述 给定一个正整数 n ，表示一个国家的城市数量。再给定一列整数 a 1 , a 2 ,⋯, a n ，表示每个城市生产或者消费物资的数量，正数表示生产数量，负数表示消费数量。输入数据保证生产总量和消费总量是相等的，即 a 1 + a 2 +⋯+ a n =0 。 这些物资可以从一个城市搬运到另一个城市，一次搬运必须在两个编号相邻的城市间进行，若搬运一个单位数量的物资到一个相邻的城市，将产生一个单位的工作量。请设计一个方案，使得所有物资都从生产城市搬运至消费城市，且每个消费城市需要的物资数量都能得到满足，且搬运的总工作量达到最小。 输入 第一行：单个整数表示 n 。 第二行： n 个整数表示 a 1 , a 2 ,⋯, a n 。 单个整数：表示最优运输方案产生的最少工作总量。 样例输入输出 输入#1 复制 4 -10 10 20 -20 输出#1 复制 30 提示 对于 30% 的数据， 1≤n≤10 ； 对于 60% 的数据， 1≤n≤100 ； 对于 100% 的数据， 1≤n≤100000 ， −100000≤ a i ≤100000 ；

以下是这道题的 C++ 代码实现：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int left = 0, right = n - 1;
    int ans = 0;
    while (left < right) {
        // 找到第一个需要消费的城市
        while (a[left] >= 0) left++;
        // 找到第一个需要生产的城市
        while (a[right] <= 0) right--;
        // 计算当前两个城市之间的搬运工作量
        int t = min(-a[left], a[right]);
        ans += t * (right - left);
        a[left] += t;
        a[right] -= t;
        // 如果某个城市已经满足需求，则向前移动指针
        if (a[left] == 0) left++;
        if (a[right] == 0) right--;
    }
    cout << ans << endl;
    return 0;
}

该算法的时间复杂度为 O(n)，可以通过本题。