CSP 202112-1 序列查询

 答题

这道题不难，但如果直接去实现查询f（x）的话，算法效率会非常低

我们直接观察样例，15=（5-2）*1+（8-5）*2+（10-8）*3

所以我们可以写出下面程序

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