五级考题
2025-12-28 19:08:01
发布于：广东
4阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
long long n,a[N],psum,ans;
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i],psum+=a[i];
psum/=n;
for(int i=1;i<=n;i++){
ans+=abs(a[i]-psum);
}
cout<<ans;
return 0;
}
//给你n数字总共偶数个,且每个数字会出现一次重复
//考察动态规划(dp)
//可以将a[i]移动到任意位置,消耗为a[i],求所有相同数字相邻的最少消耗
//1 3 4 5 4 3 1 2 5 2
//5 1 2 5 4 4 1 2
//如果想要相同的两个数字不移动相邻,则需要将[l+1,r-1]之间的所有数字全部移动或者主动移动a[i]求最优
//ans[i]求前i个数字完成的最小花费,或者求最多多少个不重复区间
//状态转移方程,对于对称点i,j(j<i)
//最终的状态转移方程ans[i]=min(ans[i-1],ans[j-1]+sum(a[(j,i)],a[i]+ans[i]-ans[j-1]);
//给你n个数字,每个数字可以*x或者/x,x是素数每次执行消耗x,问最小消耗,使得所有数字相同
//质因式分解定理
//for(int i=2;i*i<=n;i++){
// while(n%i==0){
// n/=i;
// }
// }
//10 20
// 2 5 22 5
//1 2
//n 10 2*5
// 20 2^2*5;
//将一个数字分解为素数乘积
//2 8 4 16
//1 3 2 4
//最终求解的题目为
/*C++题目：
有一个包含n(n<2e5)个数的数列，你可以对数列里的任意数+1或-1，
每次操作耗费一个金币。问：最少需要多少金币可以让数列的所有数相等，最后输出所花金币数。
输入格式：
第一行输入一个n。
第二行输入n个a[i](a[i]<30)。
输出格式：
输出一个整数，表示最少所花金币数*/
这里空空如也
有帮助，赞一个