第24次CCF CSP考试第一题

序列查询

题目背景

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

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

题目描述

A=[A0,A1,A2,?,An] 是一个由 n+1 个 [0,N) 范围内整数组成的序列，满足 0=A0

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

1. 存在下标 0≤i

此时序列 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)=∑i=0N?1f(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输入

3 10
2 5 8

样例1输出

15

样例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

样例2输出

45

子任务

50% 的测试数据满足 1≤n≤200 且 n

全部的测试数据满足 1≤n≤200 且 n

提示

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

------------------------------------------------------------------------

题解

暴力

懒得优化，先直接尝试暴力

#include 
using namespace std;

const int N = 1e7 + 10;

int n, m;
int a[220],s[N]; // 定义s数组求前缀和

int find(int x) // 定义find函数来寻找小于等于x的Ai序列下标
{
    int l = 0, r = n;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return a[l] <= x ? l : l - 1; // 存在下标小于x的情况，因此需要特判
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i < m; i ++ ) s[i] = find(i) + s[i - 1];
    printf("%d\n", s[m - 1]);
    return 0;
}

发现通过了

优化

用i去遍历A序列。题目中f(x)的值本质上对应的的是A序列中满足条件的最大下标,即a[i] 到 a[i - 1]中可以存在几个x

因此：
1.满足连续f(x)的值相同的个数为 a[i] - a[i - 1]个；
2.f(x)对应的值为a数组左边最近一个数的下标 i - 1；
3.循环统计到 i = n 就停止了，但是求和还需要继续求到 m 之前。

#include 
using namespace std;

int n, m, res;
int a[220];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) 
    {
        scanf("%d", &a[i]);
        res += (i - 1) * (a[i] - a[i - 1]); // 求出a[n]之前各项f(x)对应的值的和
    }
    printf("%d\n", res + (m - a[n]) * n); // 在最后加上a[n]右边各项f(x)对应的值直到边界m
    return 0;
}

优化成功，acwing上也过掉了