显然，操作的方式一定是一段数字相等的极长连续段向左右拓展（包括长度为 \(1\) 的段）。故只需扫一遍并维护每段的值和长度即可，并更新答案。时间复杂度 \(O(\sum n)\)。
#include<iostream>
#include<cstdio>
#define int long long
#define N 500010
using namespace std;
int n,a[N],b[N],cnt,lst,ans;
void solve(){cin>>n;ans=1e18;cnt=0;lst=0;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){if(a[i]==a[i-1]){cnt++;lst=a[i];}else{if(lst) ans=min(ans,lst*(n-cnt));// cout<<lst<<' '<<cnt<<' '<<lst*(n-cnt)<<endl;cnt=1;lst=a[i];}}if(lst)ans=min(ans,lst*(n-cnt));cout<<ans<<'\n';return;
}
signed main(){int T;cin>>T;while(T--)solve();return 0;
}
)
底层原理详解)
)
)
