首页 > 试题广场 >

割韭菜问题

[编程题]割韭菜问题
  • 热度指数：97 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小明种了一排共 n 棵韭菜，初始时所有韭菜的高度均为 0。
每棵韭菜有一个固定的生长速度 h_i，表示单位时间内该韭菜会长高 h_i 的高度。
现在小明要进行 m 次收割操作，每次收割操作会指定一个时间点 t_i 和一个区间 [l_i, r_i]，表示在时刻 t_i 收割第 l_i 棵到第 r_i 棵（包含边界）的韭菜，收割后这些韭菜的高度变为 0。
小明想知道在所有收割操作完成后，他总共收割了多少高度的韭菜。

输入描述:
第一行包含两个整数 n 和 m，分别表示韭菜的数量和收割操作的次数。
第二行包含 n 个整数 h_1, h_2, \ldots, h_n，表示每棵韭菜的生长速度。
接下来 m 行，每行包含三个整数 t_i, l_i, r_i，表示在时刻 t_i 收割第 l_i 棵到第 r_i 棵韭菜。


输出描述:
输出一个整数，表示在所有收割操作完成后，小明总共收割了多少高度的韭菜。
示例1

输入

3 2
1 2 3
1 1 2
2 2 3

输出

11
算法知识视频讲解
添加回答
不会拉粑粑的巴啦啦小魔仙头像 不会拉粑粑的巴啦啦小魔仙
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    int m;
    while (cin >> n >> m) {
        vector<int> v1(n, 0);
        vector<vector<int>> v2(m, vector<int>(3));
        for (int i = 0; i < n; ++i) {
            cin >> v1[i];
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < 3; ++j) {
                cin >> v2[i][j];
            }
        }
        sort(v2.begin(),v2.end(),[](const vector<int>& a1,const vector<int>& a2){
            return(a1[0]<a2[0]);
        });
        vector<int> v3(n, 0);
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            if (i >= (v2[0][1] - 1) && i < v2[0][2]) {
                v3[i] += v2[0][0] * v1[i];
                sum += v3[i];
                v3[i] = 0;
            } else {
                v3[i] += v2[0][0] * v1[i];
            }
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (j >= v2[i][1] - 1 && j < v2[i][2]) {
                    v3[j] += (v2[i][0] - v2[i - 1][0]) * v1[j];
                    sum += v3[j];
                    v3[j] = 0;
                } else {
                    v3[j] += (v2[i][0] - v2[i - 1][0]) * v1[j];
                }
            }
        }
        cout << sum << endl;
    }
}
大数据过不去没办法，时间复杂度偏高，注意数据是否随时间升序
发表于 2026-03-06 20:30:40 回复(0)
提交观点

问题信息

难度：
1条回答 112浏览

热门推荐

相关试题

割韭菜问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号