[C++知识库]CCF CSP —— 序列查询【202112-1】

样例1输入

3 10
2 5 8

样例1输出

15

样例2输入

9 10
1 2 3 4 5 6 7 8 9

样例2输出

45

我的代码

整理博客看到提示后修改的代码?主要优化在了空间使用上，从40.72MB到2.792MB

#include <iostream>
using namespace std;

int main(){
    int n, N;
    cin >> n >> N;
    int previous = 0; // A[0] = 0
    int answer = 0;
    for (int i = 0; i < n; i++) {
        int current;
        cin >> current;
        answer += (current - previous) * i;
        previous = current;
    }
    answer += (N - previous) * n;
    cout << answer;
    return 0;
}

原先代码
f[i]: 存储数组A中值小于等于i的A数组的最大下标

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

// 修改f[]数组的值，处理A(i) <= x <= A(i+1)的情况
void changeIndex(vector<int>& f, int previous, int current, int index) {
    for (int i = previous; i < current; i++){
        f[i] = index;
    }
}

int main(){
    int n, N;
    cin >> n >> N;
    vector<int> f(N); // 存储[0, N)中N个数据发返回下标值
    int previous = 0; // A[0] = 0, previous用来存储A数组中的前一个值
    for (int i = 0; i < n; i++) {
        int current;
        cin >> current;
        changeIndex(f, previous, current, i);
        previous = current;
    }
    // 处理A(n) <= x的情况
    for (int i = previous; i < N; i++) {
        f[i] = n;
    }
    int answer = 0;
    for (int i = 0; i < N; i++) {
        answer += f[i];
    }
    cout << answer;
    return 0;
}