CSP 202112-1 序列查询 C++ 100

2023-01-05

题目

【题目背景】西西艾弗岛的购物中心里店铺林立，商品琳琅满目。为了帮助游客根据自己的预算快速选择心仪的商品，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。 2.An≤x 此时序列A中所有的数都小于等于x,其中最大的数为An,故f(x)=n。令sum(A)表示f(0)到f(N-1)的总和，即：

$$
sum(A)=∑f(i)=f(0)+f(1)+f(2)+···+f(N-1)
$$

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

【输入格式】从标准输入读入数据。输入的第一行包含空格分隔的两个正整数n和N。输入的第二行包含n个用空格分隔的整数A1,A2,···,An 注意 A0 固定为 0，因此输入数据中不包括A0。

【输出格式】输出到标准输出。仅输出一个整数，表示 sum(A) 的值。

【样例输入】

1 2	3 10 2 5 8

【样例输出】

代码

#include <iostream>

using namespace std;
/*
int fun_x(int x)
{
    int start_i;
    fun_x(x-1)
    for(int i=start_i)
}*/

int main()
{
    int A[201];
    int i,j,N,n,sum,f;

    cin>>n>>N;
    A[0]=0;
    for(int i=0;i<n;i++)
    {
        cin>>A[i+1];
    }
    i=0;
    j=0;
    f=0;
    sum=0;
    while(i<N)
    {
        if(j+1<=n)
        {
            sum+=(A[j+1]-A[j])*f;
            j++;
            f=j;
            i=A[j];
        }
        else
        {
            sum+=(N-A[j])*f;
            i=N;
        }
    }
    cout<<sum<<endl;
    return 0;
}