题目
代码
#include<bits/stdc++.h>
using namespace std;
int n,N;
int A[100010]={0};
long long erro=0;
int r;
int main()
{
scanf("%d%d",&n,&N);
for(int i=1;i<=n;i++)
{
scanf("%d",&A[i]);
}
n++;
A[n++]=N;
r=floor(N/(n-1));
int left,right,mid;
int f=0;
for(int i=1;i<n;i++)
{
left=A[i-1];
mid=left;
right=A[i]-1;
if((left/r)!=(right/r))
{
for(mid=left+(r-left%r-1);mid<=right;mid+=r)
{
erro+=abs(((left/r)-f))*(mid-left+1);
left=mid+1;
}
erro+=abs(((right/r)-f))*(right-left+1);
}
else
{
erro+=abs((left/r)-f)*(right-left+1);
}
f++;
}
printf("%lld",erro);
return 0;
}
运行截图
思路
做这个题一开始考虑的是肯定和差分或者是前缀和有关（对数组进行多次查询），因此考虑差分减法，但通过差分找规律后找到了第一个题的简便做法：
#include<bits/stdc++.h>
using namespace std;
int n,N;
int num;
long long result=0;
int main() {
scanf("%d%d",&n,&N);
result=n*N;
for(int i=1;i<=n;i++)
{
scanf("%d",&num);
result-=num;
}
printf("%d",result);
return 0;
}
但上述方法没有办法解决第二题，暴力解题只有七十分，暴力解题只有一重循环，考虑用N太浪费时间，发现如果用n进行循环，时间就不会超出限制，又能够发现A[i-1]~A[i]内f的值都是一样的，所有的g的值其实就是i/r的整数部分，因此一开始想到把全部的f的值加起来，g的值加起来作差就行，但最后发现不对，因为中间有些做完差后需要取绝对值
就考虑在已经分好的 A[i-1]~A[i]区间内再去找哪一部分大于g（这里由前面推论可知g的值和i有关，因此分别求出左右两端的区间端点g值判断划分即可）,然后再以r为区间长度进行循环求解，得出答案。
