自己认为比较好理解的计算方法:
根据第一题的计算过程,定位到f相同的段,然后在相同f段中找出g不同的段分别计算。
- 在f相同段中,计算出两侧的g1,g2
- 如果g1,g2相同则直接计算
- 如果g1,g2不同,分段计算
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n, m;
long long ans;
int main()
{
cin >> n >> m;
a[n + 1] = m;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
int r = m / (n + 1);
// 按照f分段
for (int i = 0; i <= n; i ++ ) {
int g1 = a[i] / r + 1;
long long res1 = r - a[i] % r;
int g2 = a[i + 1] / r - 1;
long long res2 = a[i + 1] % r;
// 按照g分段
for (int j = g1; j <= g2; j ++ ) {
ans += abs(j - i) * r;
}
// 特判当a[i]和a[i + 1]在相同g中时,直接计算,这里我自己最开始没考虑,调试很久,差点崩溃
if (g1 - 1 == g2 + 1) {
ans += abs(g1 - 1 - i) * (a[i + 1] - a[i]);
}
else {
ans += abs(g1 - 1 - i) * res1;
ans += abs(g2 + 1 - i) * res2;
}
}
cout << ans;
return 0;
}