打扫
题目描述
枫同学是一个很喜欢整洁的人。
她看到茜同学留下的一排数字，决定把这些数字收拾整齐然后狠狠教训茜同学。
具体来说，茜同学留下了一个长度 n 的数组[ a 1 , a 2 , ⋯ , a n ] [a_1, a_2, \cdots, a_n][a1,a2,⋯,an]，枫同学选择了三个整洁的数x , y , z x, y, zx,y,z。
她每次可以选择一个 a 中的元素a i a_iai，将a i a_iai换成a i + 1 a_i + 1ai+1。
她决定让这个数组中至少各有一个元素是x xx的倍数，y yy的倍数和z zz的倍数。
她想尽快弄完去找茜同学，问你她至少要多少次操作才能满足要求？
输入格式
输入第一行四个整数n , x , y , z n, x, y, zn,x,y,z。
第二行n nn个整数，代表数组[ a 1 , a 2 , ⋯ , a n ] [a_1, a_2, \cdots, a_n][a1,a2,⋯,an]。
输出格式
输出一行一个整数，代表满足要求需要的最少操作次数。
数据范围
对于30 % 30\%30%的数据，n ≤ 10 n \le 10n≤10；
对于另外30 % 30\%30%的数据，x = y x = yx=y；
对于100 % 100\%100%的数据，1 ≤ n ≤ 2 × 10 5 , 1 ≤ x , y , z ≤ 10 6 , 1 ≤ a i ≤ 10 18 1 \le n \le 2 \times 10^5, 1 \le x, y, z \le 10^6, 1 \le a_i \le 10^{18}1≤n≤2×105,1≤x,y,z≤106,1≤ai≤1018。
样例
样例1
输入：
6 2 3 5 1 1 4 5 1 4输出：
2样例2
输入：
5 6 10 14 1 9 1 9 8输出：
10题解
这个题真的不想说什么了。
#include<iostream>#include<vector>#include<algorithm>#include<climits>#include<utility>usingnamespacestd;// 统一类型定义，避免溢出和类型混乱typedeflonglongll;// 步数+索引的键值对，first=步数，second=元素下标typedefpair<ll,int>pli;// 题目中最大步数不超过1e6，3个步数和最大3e6，用1e18作为极大值完全安全（无溢出）constll INF=1e18;// 欧几里得算法求GCD（适配long long）llgcd(ll a,ll b){while(b){ll tmp=b;b=a%b;a=tmp;}returna;}// 求LCM，先除后乘彻底避免溢出（题目中x/y/z≤1e6，LCM最大为1e12，long long可存）lllcm(ll a,ll b){if(a==0||b==0)return0;returna/gcd(a,b)*b;}// 提取前k个最小的(步数,索引)，自动处理n<k的边界情况vector<pli>get_top_k(constvector<pli>&vec,intk){vector<pli>res=vec;// 按步数升序，步数相同按索引升序（不影响结果，仅统一排序规则）sort(res.begin(),res.end(),[](constpli&a,constpli&b){if(a.first!=b.first)returna.first<b.first;returna.second<b.second;});// 若元素数量不足k，直接返回所有元素if((int)res.size()>k)res.resize(k);returnres;}// 从指定列表中，找除了exclude_idx外的最小步数（用于次小值获取）llget_min_exclude(constvector<pli>&vec,intexclude_idx){ll min_val=INF;for(constauto&p:vec){if(p.second!=exclude_idx&&p.first<min_val){min_val=p.first;}}returnmin_val;}intmain(){// 输入加速（处理2e5数据必备，关闭cin/stdio同步）ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);intn;ll x,y,z;cin>>n>>x>>y>>z;vector<ll>arr(n);for(inti=0;i<n;++i){cin>>arr[i];}// 预计算所有公倍数ll lcm_xy=lcm(x,y);ll lcm_xz=lcm(x,z);ll lcm_yz=lcm(y,z);ll lcm_xyz=lcm(lcm_xy,z);// 存储每个元素的各类步数+索引（单值/两两组合）vector<pli>s_x,s_y,s_z;vector<pli>s_xy,s_xz,s_yz;// 存储单元素满足三者的步数（仅存值，下标由循环确定）vector<ll>s_xyz(n,INF);// 遍历计算每个元素的所有步数（核心公式无错，保留）for(inti=0;i<n;++i){ll num=arr[i];// 单值步数：(k - num%k) % k 确保num是k倍数时步数为0autocal=[&](ll k)->ll{if(k==0)return0;ll mod=num%k;returnmod==0?0:(k-mod);};ll sx=cal(x),sy=cal(y),sz=cal(z);ll sxy=cal(lcm_xy),sxz=cal(lcm_xz),syz=cal(lcm_yz);ll sxyz=cal(lcm_xyz);s_x.emplace_back(sx,i);s_y.emplace_back(sy,i);s_z.emplace_back(sz,i);s_xy.emplace_back(sxy,i);s_xz.emplace_back(sxz,i);s_yz.emplace_back(syz,i);s_xyz[i]=sxyz;}// ========== 组合1：三个不同元素分别满足x、y、z（核心） ==========ll min_3=INF;// 取前3个最小值即可，枚举3*3*3=27次，无性能损耗vector<pli>top3_x=get_top_k(s_x,3);vector<pli>top3_y=get_top_k(s_y,3);vector<pli>top3_z=get_top_k(s_z,3);// 枚举所有组合，筛选索引互不相同的有效组合for(constauto&px:top3_x){for(constauto&py:top3_y){for(constauto&pz:top3_z){intix=px.second,iy=py.second,iz=pz.second;// 三个索引互不相同，且步数均为有效值if(ix!=iy&&iy!=iz&&ix!=iz){min_3=min(min_3,px.first+py.first+pz.first);}}}}// ========== 组合2-4：两个不同元素（一个满足两两，一个满足单值） ==========// 辅助函数：计算「两两组合min + 单值min」的最小有效和（索引不同）autocal_two=[&](constvector<pli>&s_double,constvector<pli>&s_single)->ll{// 找两两组合的最小值pli min_double=*min_element(s_double.begin(),s_double.end());// 找单值的最小值pli min_single=*min_element(s_single.begin(),s_single.end());ll res=INF;// 索引不同，直接相加if(min_double.second!=min_single.second){res=min(res,min_double.first+min_single.first);}else{// 索引相同，找次小值：要么换两两组合，要么换单值ll sub_double=get_min_exclude(s_double,min_single.second);ll sub_single=get_min_exclude(s_single,min_double.second);if(sub_double!=INF)res=min(res,sub_double+min_single.first);if(sub_single!=INF)res=min(res,min_double.first+sub_single);}returnres;};ll min_2_xy_z=cal_two(s_xy,s_z);// xy + zll min_2_xz_y=cal_two(s_xz,s_y);// xz + yll min_2_yz_x=cal_two(s_yz,s_x);// yz + x// ========== 组合5：单个元素满足x、y、z ==========ll min_1_xyz=INF;for(ll val:s_xyz){min_1_xyz=min(min_1_xyz,val);}// ========== 所有有效组合取最小值 ==========ll ans=INF;ans=min(ans,min_3);ans=min(ans,min_2_xy_z);ans=min(ans,min_2_xz_y);ans=min(ans,min_2_yz_x);ans=min(ans,min_1_xyz);cout<<ans<<endl;return0;}
