202112-2 序列查询新解

#include <bits/stdc++.h>//70分 30分运行错误
using namespace std;
const int maxn = 100005;
int n, N;
int a[maxn];
int f[maxn];
int g[maxn];
 
int main()
{
   cin >> n >> N;
   a[0] = 0;
   for (int i = 1; i <= n; i++)
   {
      cin >> a[i];
      f[a[i]] = f[a[i - 1]] + 1;
   }
   for (int i = 0; i < N; i++)
   {
      if (f[i] == 0)
         f[i] = f[i - 1];
   }
   int r=N/(n+1);
   for (int i = 0; i < N; i++)
   {
      g[i]=i/r;
   }
   int sum=0;
   for (int i = 0; i < N; i++)
   {
      sum+=abs(g[i]-f[i]);
   }
   cout<<sum;
  
}

#include <bits/stdc++.h> //分段思想
using namespace std;
typedef long long int ll;
const int maxn = 150000;
int n, N;
int a[maxn];
 
int main()
{
   cin >> n >> N;
   a[0] = 0;
   for (int i = 1; i <= n; i++)
   {
      cin >> a[i];
   }
   a[n + 1] = N;
   int r = N / (n + 1);
   long long sum = 0;
   for (int i = 0; i <= n; i++)
   {
      long long sum1 = 0, sum2 = 0;
      for (int j = a[i]; j < a[i + 1];)
      {
         int num = j / r; // g此时的值
         int cnt = r - j % r;//区间内共多少值
         cnt = min(cnt, a[i + 1] - j);
         sum1 = cnt * i;
         sum2 = cnt * num;
         sum+=abs(sum1-sum2);
         j+=cnt;
      }
   }
   cout<<sum;
}