202112-1
#include<iostream>
using namespace std;
#define N 1e7
int a[201];
int n;
int f(int x)
{
int flag=0;
for(int i=0;i<n;i++)
{
if(a[i]<=x&&x<a[i+1])
{
return i;
flag=1;
break;
}
}
if(flag==0) return n;
}
int main()
{
int m;
int sum=0;
cin>>n>>m;
a[0]=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=0;i<n;i++)
{
sum+=f(a[i])*(a[i+1]-a[i]);
}
sum+=f(a[n])*(m-a[n]);
cout<<sum<<endl;
return 0;
}
202112-2
70分题解：
#include<iostream>
#include<cmath>
using namespace std;
#define N 100001
const int M=1e5;
int a[N];
long long f[M];
long long g[M];
int n,m;
int r;
int ff(int x)
{
int flag=0;
for(int i=0;i<n;i++)
{
if(a[i]<=x&&x<a[i+1])
{
return i;
flag=1;
break;
}
}
if(flag==0) return n;
}
int main()
{
cin>>n>>m;
a[0]=f[0]=0;
int err=0;
r=m/(n+1);
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=0;i<m;i++)
{
f[i]=ff(i);
g[i]=i/r;
err+=abs(f[i]-g[i]);
}
/* for(int i=n;i<m;i++)
{
f[i]=n;
g[i]=i/r;
err+=abs(f[i]-g[i]);
}*/
cout<<err<<endl;
return 0;
}
100分（注：sum用int定义依旧70分，用long long定义100分）
#include<iostream>
#include<cmath>
using namespace std;
#define N 100001
int a[N];
int n,m;
int Long=0;
int r;
long long sum=0;
long long g(int x)
{
return x/r;
}
int main()
{
cin>>n>>m;
a[0]=0;
a[n+1]=m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
r=m/(n+1);
for(int i=1;i<=n+1;i++){//以f(i)为区域划分计算
long long sum1=0;//记录此小区间差值的和
for(int j=a[i-1];j<=a[i]-1;j=j+Long){//此区间内有Long个g取值为g(j)的数
int NumEnd=(g(j)+1)*r-1;//g取值为g(j)最大的数为NumEnd
if(NumEnd>a[i]-1) NumEnd=a[i]-1;//上界超出范围，变为区间最上界
int NumLong=NumEnd-j+1;//取值为g(j)的数为NumLong个
long long f_g=abs(i-1-g(j));//f与g差值，f值恒为i-1
sum1=sum1+f_g*NumLong;
Long=NumLong;
}
sum=sum+sum1;
}
cout<<sum<<endl;
return 0;
}
