题目
过程
第一次提交
#include<bits/stdc++.h>
using namespace std;
long long n,N;
int main()
{
cin>>n>>N;
long long A[n+1];
long long f[N];
long long g[N];
A[0]=0;
long long 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;
}
}
for(int j=A[n];j<N;j++)
{
f[j]=n;
}
long long r=floor(N/(n+1));
// cout<<"r="<<r<<endl;
for(int x=0;x<N;x++)
{
g[x]=floor(x/r);
//cout<<"g[x]="<<g[x]<<" ";
long long temp=abs(g[x]-f[x]);
//cout<<"temp="<<temp<<endl;
sum+=temp;
//cout<<sum<<endl;
}
cout<<sum;
return 0;
}
运行错误,得70分,一开始以为提示中说error会很大,所以把所有的int类型改成了long long类型,但是并没有什么用,样例测试都正确但仍然70分。
第二次提交
#include<bits/stdc++.h>
using namespace std;
int n,N;
long long f[1000100],g[1000100];
int main()
{
cin>>n>>N;
long long A[n+1];
// long long f[N];
// long long g[N];
A[0]=0;
long long 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;
}
}
for(int j=A[n];j<N;j++)
{
f[j]=n;
}
int r=floor(N/(n+1));
// cout<<"r="<<r<<endl;
for(int x=0;x<N;x++)
{
g[x]=floor(x/r);
//cout<<"g[x]="<<g[x]<<" ";
long long temp=abs(g[x]-f[x]);
//cout<<"temp="<<temp<<endl;
sum+=temp;
//cout<<sum<<endl;
}
cout<<sum;
return 0;
}
重新开辟数组 ,这次是运行超时,70分。推测之前是数据太大爆了。
第三次提交
#include<bits/stdc++.h>
using namespace std;
int n,N;
long long sum=0;
int r;
int main()
{
cin>>n>>N;
r=N/(n+1);
int a=0,b;//a:当前值,b:前一个值
int len; //len:g(x)连续相同值的长度
for(int i=1;i<=n;i++)
{
b=a;
cin>>a;
for(int j=b;j<a;j=j+len)
{
len = (j / r + 1) * r - j;
if(j<a&&j+len>a)
{
len=a-j;
}
sum=sum+len*abs(j/r-i+1);
}
}
for(int i=a;i<N;i=i+len)
{
len = (i / r + 1) * r - i;
if(i<N&&i+len>N)
{
len=N-i;
}
sum=sum+len*abs(i/r-n);
}
cout<<sum<<endl;
return 0;
}