故事是这样的,我写了这道题,然后发现贪心策略假了,改了一个策略,貌似真了,但问题在于这个代码超时了,所以我想知道是我的做法本来就是假的还是我写挂了。
#include<bits/stdc++.h>
using namespace std;
/*
Author: EnderSnow
OnlineJudge: Luogu/517coding
mobai: rui_er && Kals && hpdf && EnderDeer
*/
const int N=200010;
int a[N];
int b[N];
int n,m;
int tmp=0;
int mn=0x3f3f3f;
int ret=0;
int flag;
int flag2=1;
int main()
{
int ans=0;
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i];
mn=min(mn,a[i]);
if(a[i]!=a[i-1] and i-1!=0) flag2=0;
}
if(flag2==1)
{
cout<<n*a[1]<<endl;
return 0;
}
for(int i=1;i<=n;i++)
{
if(a[i]==mn)
{
flag=i;
ret++;
}
}
if(ret>1)
{
/*
sort(b+1,b+1+n);
for(int i=2;i<=n;i++)
{
if(b[i]!=b[i-1])
{
tmp=b[i];
break;
}
}
for(int i=1;i<=n;i++)
{
if(a[i]==tmp)
{
tmp=i;
break;
}
}
*/
for(int i=n;i>=1;i--)
{
if(a[i]==mn)
{
tmp=i+1;
break;
}
}
//cout<<tmp<<endl;
}
else
{
if(flag+1>n) flag=1;
else tmp=flag+1;
}
for(int i=tmp;;i++)
{
if(i==n+1) i=1;
if(a[i]==0)
{
break;
}
if(a[i]>0)
{
ans++;
a[i]-=1;
}
if(i==n+1) i=1;
}
cout<<ans<<endl;
return 0;
}