原題鏈接

解析

設 \(f_i\) 表示取完了編號為 \(a_i\) 的車，最后取出的是第 \(i\) 個格子上的車所需的最少操作次數。枚舉上一層終點 \(j\) 進行轉移：

其中 \(\operatorname{dis}(i,j)\) 表示從第 \(i\) 個格子走到第 \(j\) 個格子所需的最少步數，\(\operatorname{CW}(i,j)\) 和 \(\operatorname{ACW}(i,j)\) 分別表示從 \(i\) 順、逆時針走到 \(j\) 的步數，\(pre_i,nxt_i\) 分別表示在 \(i\) 之前逆時針和 \(i\) 之后順時針第一個編號為 \(a_i\) 的位置。

這樣直接轉移復雜度是 \(O(n)\) 的，考慮優化，以 \(f_j + \operatorname{dis}(pre_i,j) + \operatorname{ACW}(pre_i,i)\) 為例，先把和 \(j\) 有關的項提取出來：

拆開 \(\operatorname{dis}\) 變為：

欽定 \(pre_i > j\) 拆絕對值：

只考慮跟 \(j\) 有關的項，求出 \(f_j - j\) 和 \(f_j + j\) 的前綴最小值再加上二分就可以做到 \(O(\log n)\) 轉移。\(pre_i \le j\) 的情況同理，詳見代碼。

代碼

時間復雜度 \(O(n\log n)\)。當然你也可以用雙指針替代二分從而省下轉移過程中的 \(\log\)。

#include <bits/stdc++.h>
#define ls(x) ((x) << 1)
#define rs(x) (((x) << 1) | 1)
#define mid ((l + r) >> 1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e6 + 5,M = 100 + 5,mod = 998244353;
int a[N],pre[N],nxt[N];
ll f[N],premn1[N],premn2[N],sufmn1[N],sufmn2[N];
vector<int> pos[N];
int n;
int CW(int a,int b){
	if(b >= a) return b - a;
	return n - (a - b);
}
int ACW(int a,int b){
	if(a >= b) return a - b;
	return n - (b - a);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	memset(f,127,sizeof(f));
	memset(premn1,127,sizeof(premn1));
	memset(premn2,127,sizeof(premn2));
	memset(sufmn1,127,sizeof(sufmn1));
	memset(sufmn2,127,sizeof(sufmn2));
	cin>>n;
	vector<int> v;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		v.push_back(a[i]);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	for(int i=1;i<=n;i++){
		a[i] = lower_bound(v.begin(),v.end(),a[i]) - v.begin() + 1;
		pos[a[i]].push_back(i);
	}
	for(int i=1;i<=v.size();i++){
		for(int j=0;j<pos[i].size();j++){
			if(j)
				pre[pos[i][j]] = pos[i][j - 1];
			if(j + 1 < pos[i].size())
				nxt[pos[i][j]] = pos[i][j + 1];
		}
		pre[pos[i][0]] = pos[i].back();
		nxt[pos[i].back()] = pos[i][0];
	}
	pos[0].push_back(0);
	f[0] = 0;
	premn1[0] = sufmn1[0] = 1;
	premn2[0] = sufmn2[0] = -1;
	ll res = 9e18;
	for(int i=1;i<=v.size();i++){
		for(int j : pos[i]){
			auto it = lower_bound(pos[i - 1].begin(),pos[i - 1].end(),pre[j]);//pre[j] < k
			int k = pos[i - 1].back();
			//f[k] + min(k - pre[j],n - k + pre[j])
			if(it != pos[i - 1].end()){
				k = *it;
				f[j] = min(f[j],min(sufmn1[k] - pre[j],n + sufmn2[k] + pre[j]) + ACW(pre[j],j));
			}
			if(k > pre[j]) k = pre[k];
			if(k < pre[j]){
				//pre[j] > k
				//f[k] + min(pre[j] - k,n - pre[j] + k)
				f[j] = min(f[j],min(premn2[k] + pre[j],n + premn1[k] - pre[j]) + ACW(pre[j],j));
			}
			it = lower_bound(pos[i - 1].begin(),pos[i - 1].end(),nxt[j]);
			k = pos[i - 1].back();
			if(it != pos[i - 1].end()){
				k = *it; 
				f[j] = min(f[j],min(sufmn1[k] - nxt[j],n + sufmn2[k] + nxt[j]) + CW(nxt[j],j));
			}
			if(k > nxt[j]) k = pre[k];
			if(k < nxt[j]){
				f[j] = min(f[j],min(premn2[k] + nxt[j],n + premn1[k] - nxt[j]) + CW(nxt[j],j));
			}
			premn1[j] = f[j] + j,premn2[j] = f[j] - j;
			if(pre[j] < j){
				premn1[j] = min(premn1[j],premn1[pre[j]]);
				premn2[j] = min(premn2[j],premn2[pre[j]]);
			}
			if(i == v.size()){
				res = min(res,f[j]);
			}
		}
		for(int j=pos[i].size() - 1;j>=0;j--){
			int t = pos[i][j];
			sufmn1[t] = f[t] + t,sufmn2[t] = f[t] - t;
			if(j < pos[i].size() - 1){
				sufmn1[t] = min(sufmn1[t],sufmn1[nxt[t]]);
				sufmn2[t] = min(sufmn2[t],sufmn2[nxt[t]]);
			}
		}
	}
	cout<<res;
	return 0;
}