序列查询【CSP】202112-1

傷城~ 2023-09-28 15:30 9阅读 0赞

### 题目背景 ###

西西艾弗岛的购物中心里店铺林立，商品琳琅满目。为了帮助游客根据自己的预算快速选择心仪的商品，IT 部门决定研发一套商品检索系统，支持对任意给定的预算 x，查询在该预算范围内（≤x）价格最高的商品。如果没有商品符合该预算要求，便向游客推荐可以免费领取的西西艾弗岛定制纪念品。

假设购物中心里有 n 件商品，价格从低到高依次为 A1,A2⋯An，则根据预算 x 检索商品的过程可以抽象为如下序列查询问题。

### 题目描述 ###

A=\[A0,A1,A2,⋯,An\] 是一个由 n+1 个 \[0,N) 范围内整数组成的序列，满足 0=A0<A1<A2<⋯<An<N。（这个定义中蕴含了 n 一定小于 N。）

基于序列 A，对于 \[0,N) 范围内任意的整数 x，查询 f(x) 定义为：序列 A 中**小于等于** x 的整数里**最大**的数的**下标**。具体来说有以下两种情况：

1.  存在下标 0≤i<n 满足 Ai≤x<Ai+1

此时序列 A 中从 A0 到 Ai 均小于等于 x，其中最大的数为 Ai，其下标为 i，故 f(x)=i。

1.  An≤x

此时序列 A 中所有的数都小于等于 x，其中最大的数为 An，故 f(x)=n。

令 sum(A) 表示 f(0) 到 f(N−1) 的总和，即：![308f42fc52cc45ba9fc1a7a0d7019e7b.png][]

对于给定的序列 A，试计算 sum(A)。

### 输入格式 ###

从标准输入读入数据。

输入的第一行包含空格分隔的两个正整数 n 和 N。

输入的第二行包含 n 个用空格分隔的整数 A1,A2,⋯,An。

注意 A0 固定为 0，因此输入数据中不包括 A0。

### 输出格式 ###

输出到标准输出。

仅输出一个整数，表示 sum(A) 的值。

### 样例1输入 ###

3 10
    2 5 8

Data

### 样例1输出 ###

Data

### 样例1解释 ###

A=\[0,2,5,8\]

如上表所示，sum(A)=f(0)+f(1)+⋯+f(9)=15。

考虑到 f(0)=f(1)、f(2)=f(3)=f(4)、f(5)=f(6)=f(7) 以及 f(8)=f(9)，亦可通过如下算式计算 sum(A)：  
sum(A)=f(0)×2+f(2)×3+f(5)×3+f(8)×2

### 样例2输入 ###

9 10
    1 2 3 4 5 6 7 8 9

Data

### 样例2输出 ###

Data

### 子任务 ###

50% 的测试数据满足 1≤n≤200 且 n<N≤1000；

全部的测试数据满足 1≤n≤200 且 n<N≤10^7。

### 提示 ###

若存在区间 \[i,j) 满足 f(i)=f(i+1)=⋯=f(j−1)，使用乘法运算 f(i)×(j−i) 代替将 f(i) 到 f(j−1) 逐个相加，或可大幅提高算法效率。

# include<iostream>
    using namespace std;
    int A[201];
    int main() {
    	int n, N,sum_A = 0;
    	cin >> n >> N;
    	int j = 0;
    	for (int i = 1; i <= n; i++) {
    		cin >> A[i];
    		sum_A += (i-1) * (A[i] - A[i - 1]);
    	}
    	sum_A += n * (N - A[n]);
    	cout << sum_A;
    	return 0;
    }

[308f42fc52cc45ba9fc1a7a0d7019e7b.png]: https://img-blog.csdnimg.cn/308f42fc52cc45ba9fc1a7a0d7019e7b.png