C++(g++ 7.5.0) 解法, 执行用时: 21ms, 内存消耗: 2248K, 提交时间: 2022-09-06 20:50:38

#include <cstdio>
#include <algorithm>

#define orep(i,a,b)  for(auto i=(a); i< (b); ++i)
#define crep(i,a,b)  for(auto i=(a); i<=(b); ++i)
#define NL           putchar(10);
#define REDIR        freopen("data.in", "r", stdin);

int main() {
  int n, m; scanf("%d%d", &n, &m);
  long long dp[m*2+2]={};
  int arr[n+1]; scanf("%d", arr+1);
  long long rst = 0;
  crep(i, 2, n) {
    scanf("%d", arr+i);
    const int l = arr[i-1], r = arr[i]<l ? arr[i]+m : arr[i];
    rst += r-l;
    if (r > l+1) {
      dp[l+2] += 1;
      dp[r+1] -= r-l;
      dp[r+2] += r-l-1;
    }
  }
  crep(i, 1, m*2) { dp[i] += dp[i-1]; }
  crep(i, 1, m*2) { dp[i] += dp[i-1]; }

  long long diff = -1;
  crep(i, 1, m) { 
    diff=std::max(diff, dp[i]+dp[i+m]);
  }

  printf("%lld", rst - diff);

  return 0;
}

C++(clang++11) 解法, 执行用时: 12ms, 内存消耗: 2768K, 提交时间: 2021-01-22 21:37:21

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e5+5,mod=1e9+7;
ll a[N],b[N<<1];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n,m;
	cin>>n>>m;
	ll tot=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(i<2)
		continue;
		int x=a[i-1],y=(a[i]>x?0:m)+a[i];
		tot+=y-x;
		if(y>=x+2)
		b[x+2]+=1,b[y+1]+=x-y,b[y+2]+=y-x-1;
	}
	for(int i=1;i<m<<1;i++)
	b[i]+=b[i-1];
	for(int i=1;i<m<<1;i++)
	b[i]+=b[i-1];
	ll mx=b[m];
	for(int i=m+1;i<m<<1;i++)
	mx=max(mx,b[i-m]+=b[i]);
	cout<<tot-mx<<endl;
	return 0;
}