上海计算机学会2024年11月月赛C++丙组T5线段数
发布时间
阅读量：
阅读量
线段数
内存限制: 512 Mb时间限制: 1000 ms
题目描述
给定数组 a=[a1,a2,⋯ ,an]，Eve 可以执行任意次（可能 0 次）以下操作：
- 选择 1≤i≤n，令 ai←ai+1。
Eve 希望最终数组中任意三个相邻元素之和都是 3 的倍数。
请求出需要达成目标所需的最小操作次数。
输入格式
第一行一个整数 n。
第二行 n 个整数 a1,⋯,an。
输出格式
一行一个整数表示答案。
数据范围
对于 30% 的数据，3≤n≤5。
对于 60% 的数据，3≤n≤1000。
对于 100% 的数据，3≤n≤105，1≤ai≤109。
样例数据
输入:
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 分别操作一次。
解析：若想要调整完的数组任意相邻三个数之和都是3的倍数，那么调整后的数组两个数的数模3的余数必然相同，即 a[i]和a[i+3]余数必然相同。我们可以分三组（i%3分别为0,1,2）统计每个数模3的余数，然后分别计算将每组都变成模3等于0,1,2的操作次数，再枚举每组变成0,1,2，判断最小操作次数，详见代码：
#include <bits/stdc++.h>
using namespace std;
int n;
int b[3][3];//b[i][j]表示模3余i的位置上的数模3余j的数的数量
int c[3][3];//c[i][j]表示将模3余i的位置上的数都变成模3余j所用的最小操作次数
int ans = 1e9;//初识化答案为最大值
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
int a;
cin >> a;
b[i % 3][a % 3]++;//计算b数组
}
for(int i = 0; i < 3; i++) {//ij枚举c数组
for(int j = 0; j < 3; j++) {
for(int k = 0; k < 3; k++) {//计算不同余数值
if (j == k) continue;//相等不用操作
if (j > k) {//结果比原来大，做j-k次操作
c[i][j] += b[i][k] * (j - k);
}
if (j < k) {//结果比原来小，做j+3-k次操作
c[i][j] += b[i][k] * (j + 3 - k);
}
}
}
}
for(int i = 0; i < 3; i++) {//枚举每组数遍更目标
for(int j = 0; j < 3; j++) {
for(int k = 0; k < 3; k++) {
//如果三组数相加能被三整除，即为成功的方案
if ((i + j + k) % 3 == 0) {
ans = min(ans, c[0][i] + c[1][j] + c[2][k]);//求最小值
}
}
}
}
cout << ans;
return 0;
}
全部评论 (0)
还没有任何评论哟~