当前位置：首页 > article >正文

11月上海月赛解报告（丙组）T5

article 2024/11/14 4:26:57

线段数

内存限制: 512 Mb时间限制: 1000 ms

题目描述

给定数组 a=[a1,a2,⋯ ,an]，Eve 可以执行任意次（可能 0 次）以下操作：

选择 1≤i≤n，令 ai←ai+1。

Eve 希望最终数组中任意三个相邻元素之和都是 3 的倍数。

请求出需要达成目标所需的最小操作次数。

输入格式

第一行一个整数 n。

第二行 nn 个整数 a1,⋯,an。

输出格式

一行一个整数表示答案。

数据范围

对于 30%30% 的数据，3≤n≤5。

对于 60%60% 的数据，3≤n≤1000。

对于 100%100% 的数据，3≤n≤10^5，1≤ai≤10^9。

样例数据

输入:

3
1 3 5

输出:

0

说明:

1+3+5=9，是 3 的倍数，不需要操作。

输入:

10
2 3 10 25 12 7 10 12 1 46

输出:

3

说明:

对 i=4,7,10 分别操作一次。

AC代码
#include<bits/stdc++.h>
using namespace std;
#define in long long
long long n,a[100005],cnt=0,ans=0,b[100005],ma=9e18;
int main(){
  cin>>n;
  for(in i=1;i<=n;i++){
  	cin>>a[i];
  	a[i]=a[i]%3;
  }
  for(int i=0;i<9;i++){
 	cnt=0;
  	in l=i/3,r=i%3;
  	for(int j=1;j<=n;j++)b[j]=a[j];
  	b[1]=(b[1]+l)%3,b[2]=(b[2]+r)%3;
  	for(in j=3;j<=n;j++){
  		cnt+=(3-(b[j-2]+b[j-1]+b[j])%3)%3;
		b[j]=(b[j]+3-(b[j-2]+b[j-1]+b[j])%3)%3;
	//	b[j]%=3;
  		
  	}
  	ma=min(ma,cnt+l+r);
  }
  cout<<ma;
  return 0;
}