题意:定义MAD为数组中至少出现两次的最大数字,如果没有就是0.给定一个长度为n的数组a,sum=0,下面的过程将依次循环执行,直到a中的所有数字都变成0:
设置sum+=∑ai;设bi=MAD(a1,a2..ai),ai=bi
求过程结束后sum的值。
分析:经历操作一次后的数组是非递减的,以后每次都是将数组向右移动,为了防止数组从左往右,不含0的第一个数字在数组里只出现1此,我们可以再执行一次操作,所以只要执行两次操作就能知道剩下的操作次数。
代码:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+10;
bool c[N];
ll n,a[N];
void g(){
for(ll i=1;i<=n;i++)c[i]=false;
ll ma=0;
for(ll i=1;i<=n;i++){
if(c[a[i]])ma=max(ma,a[i]);
c[a[i]]=true;
a[i]=ma;
}
}
void sol(){
cin>>n;
ll ans=0;
for(int i=1;i<=n;i++){
cin>>a[i];
ans+=a[i];
}
g();
for(ll i=1;i<=n;i++)ans+=a[i];
g();
for(ll i=1;i<=n;i++){
ans+=(n-i+1)*a[i];
}
cout<<ans<<endl;
}
int main(){
int t;cin>>t;
while(t--)sol();
return 0;
}