CF2107F1

思路

感觉这题的难度是严重高评的，实际难度应该只有黄，

20

分钟是绝对可以过的。

考虑贪心。

考虑如果他在

i

后面（

i>1

），且

a_{i-1}<a_i

，则交换

a_{i-1}

和

a_i

一定不劣。

所以考虑如果将

a_1

与后面的一项交换后然后再顺序枚举一遍即可。

正确性显然。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int a[N],b[N];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T,n;
	cin>>T;
	while(T--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)cin>>a[i];
		reverse(a+1,a+n+1);
		long long aans=1e18;
		for(int id=1;id<=n;id++)
		{
			for(int i=1;i<=n;i++)b[i]=a[i];
			swap(b[1],b[id]);
			long long ans=id-1+b[1];
			for(int i=2;i<=n;i++)
			{
				if(b[i]>b[i-1])
				{
					swap(b[i],b[i-1]);
					ans++;
				}
				ans+=b[i];
			}
			aans=min(ans,aans);
		}
		cout<<aans<<'\n';
	}
	return 0;
}

文章操作

思路

代码

相关推荐

评论

CF2107F1