题目

 

过程

第一次提交

暴力求解，运行超时，50分

#include<bits/stdc++.h>
using namespace std;
int n,N;
int main()
{cin>>n>>N;int A[n+1];A[0]=0;for(int i=1;i<=n;i++){cin>>A[i];}int f[N];int sum=0;for(int i=0;i<N;i++){for(int j=0;j<=n;j++){//cout<<"j="<<j<<" ";if(A[j]>i){f[i]=j-1;//	cout<<"f[i]="<<f[i]<<endl;break;}f[i]=j;}sum+=f[i];}cout<<sum;return 0;
}

第二次提交

在每次输入A[i]时就填好部分f[j]，然后直接进行查询。

#include<bits/stdc++.h>
using namespace std;
int n,N;
int main()
{cin>>n>>N;int A[n+1];int f[N];A[0]=0;int sum=0;for(int i=1;i<=n;i++){cin>>A[i];for(int j=A[i-1];j<A[i];j++){f[j]=i-1;sum+=f[j];}}for(int j=A[n];j<N;j++){f[j]=n;sum+=f[j];}cout<<sum;return 0;
}

结果