CSP 202112-2 序列查询新解 C++ 70

2023-01-05

题目

【题目背景】上一题“序列查询”中说道： A=[A0,A1,A2,,AN]是一个由n+1个[0，N)范围内整数组成的序列，满足0=A0<A1<A2<···<An<N。基于序列A,对于[O,N)范围内任意的整数x,查询f(x)定义为：序列A中小于等于x的整数里最大的数的下标。对于给定的序列A和整数x,查询f(x)是一个很经典的问题，可以使用二分搜索在O(logn)的时间复杂度内轻松解决。但在IT部门讨论如何实现这一功能时，小P同学提出了些新的想法。

【题目描述】小P同学认为，如果事先知道了序列A中整数的分布情况，就能直接估计出其中小于等于x的最大整数的大致位置。接着从这一估计位置开始线性查找，锁定(x)。如果估计得足够准确，线性查找的时间开销可能比二分查找算法更小。比如说，如果A1,A2,···,An均匀分布在(0，N)的区间，那么就可以估算出：
$$
f(x)≈{(n+1)·x}/{N}
$$

为了方便计算，小P首先定义了比例系数$r=N/{n+1}$，其中表示下取整，即r等于N除以n+1的商。进一步地，小P用g(x)=x/r表示自己估算出的(x)的大小，这里同样使用了下取整来保证g(x)是一个整数。显然，对于任意的询问x∈[O,N),g(x)和f(x)越接近则说明小P的估计越准确，后续进行线性查找的时间开销也越小。因此，小P用两者差的绝对值g(x)一f(x)来表示处理询问x时的误差。为了整体评估小P同学提出的方法在序列A上的表现，试计算：

$$
error(A)=g(0)-f(0)+···+g(N-1)-f(N-1)
$$

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

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

【样例输入】

1 2	3 10 2 5 8

【样例输出】

代码

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int A[201];
    int B[1000]={0};//f(i)-g(i)
    int i,j,N,n,r,sum;

    cin>>n>>N;
    r=int(N/(n+1));
    A[0]=0;
    for(int i=0;i<n;i++)
    {
        cin>>A[i+1];
    }
    for(i=0;i<n+1;i++)
    {

        if(i<n)
        {
            B[A[i]]+=i;
            B[A[i+1]]-=i;
        }
        else
        {
            B[A[i]]+=i;
            B[N]-=i;
        }
    }
    j=0;
    for(i=0;i<N;i=i+r)
    {
        if(i+r<N)
        {
            B[i]-=j;
            B[i+r]+=j;
        }
        else
        {
            B[i]-=j;
            B[N]+=j;
        }
        j++;
    }
    sum=0;
    for(i=1;i<N;i++)
    {
        B[i]=B[i]+B[i-1];
        sum+=abs(B[i]);
    }
    cout<<sum<<endl;
    return 0;
}