代码思路:
跟第一题一样,对每个f[i]相同的区间进行处理,将整个区间的g[i]分成三部分
以上图f[i]=1的区间[2,4]为例,将区间分成g1=A[2]/r,g2=A[4]/r,以及g在g1和g2之间这三部分
第一部分:因为每个g会出现r次,求A[2]%r可以求出当前这个值对应的g是第几次出现,在当前这个区间中还会出现r-A[2]%r次
第二部分:同理A[4]%r求出这个g是第几次出现,当前这个区间中这个g出现了A[4]%r+1次,这里要判断一次A[4]/r和A[2]/r是否相等,若相等则是同一个数,只加一次即可
第三部分:在这两个g之间的值都出现了r次
至此就可以求出这个区间所有g的值,然后就可以求出error的值,然后遍历整个区间即可
这个代码给的样例都过了,但是提交的时候只有五分,大家能看一下哪里出错了吗,感谢!
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ll ans = 0;
ll n, N;
cin >> n >> N;
ll r = N / (n + 1);
vector<ll> vec(n + 1);
vec[0] = 0;
for (ll i = 1; i <= n; i++)
{
cin >> vec[i];
}
for (ll i = 1; i <= n; i++)
{
ll f = i - 1; //[vec[i-1],vec[i])之间的f
ll a1 = vec[i - 1] / r;
ll a2 = vec[i - 1] % r;
ll b1 = (vec[i] - 1) / r;
ll b2 = (vec[i] - 1) % r;
ans += abs((r - a2) * (a1 - f));
if (b1 != a1)
ans += abs((b2 + 1) * (b1 - f));
for (ll j = a1 + 1; j < b1; j++)
ans += abs(r * (j - f));
}
ll f = n; //[vec[n],N-1]之间的f
ll a1 = vec[n] / r;
ll a2 = vec[n] % r;
N = N - 1;
ll b1 = N / r;
ll b2 = N % r;
ans += abs((r - a2) * (a1 - f));
if (b1 != a1)
ans += abs((b2 + 1) * (b1 - f));
for (ll j = a1 + 1; j < b1; j++)
ans += abs(r * (j - f));
cout << ans;
return 0;
}