one·yg99.aqq：致敬韩寒，不止于文字的青春回响
打扫题目描述枫同学是一个很喜欢整洁的人。
她看到茜同学留下的一排数字决定把这些数字收拾整齐然后狠狠教训茜同学。
具体来说茜同学留下了一个长度 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 1ai1。
她决定让这个数组中至少各有一个元素是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 yxy对于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题解这个题真的不想说什么了。
#includeiostream#includevector#includealgorithm#includeclimits#includeutilityusingnamespacestd;// 统一类型定义避免溢出和类型混乱typedeflonglongll;// 步数索引的键值对first步数second元素下标typedefpairll,intpli;// 题目中最大步数不超过1e63个步数和最大3e6用1e18作为极大值完全安全无溢出constll INF1e18;// 欧几里得算法求GCD适配long longllgcd(ll a,ll b){while(b){ll tmpb;ba%b;atmp;}returna;}// 求LCM先除后乘彻底避免溢出题目中x/y/z≤1e6LCM最大为1e12long long可存lllcm(ll a,ll b){if(a0||b
return0;returna/gcd(a,b)*b;}// 提取前k个最小的(步数,索引)自动处理nk的边界情况vectorpliget_top_k(constvectorplivec,intk){vectorpliresvec;// 按步数升序步数相同按索引升序不影响结果仅统一排序规则sort(res.begin(),res.end(),[](constplia,constplib){if(a.first!b.first)returna.firstb.first;returna.secondb.second;});// 若元素数量不足k直接返回所有元素if((int)res.size()k)res.resize(k);returnres;}// 从指定列表中找除了exclude_idx外的最小步数用于次小值获取llget_min_exclude(constvectorplivec,intexclude_idx){ll min_valINF;for(constautop:vec){if(p.second!exclude_idxp.firstmin_val){min_valp.first;}}returnmin_val;}intmain(){// 输入加速处理2e5数据必备关闭cin/stdio同步ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);intn;ll x,y,z;cinnxyz;vectorllarr(n);for(inti0;in;i){cinarr[i];}// 预计算所有公倍数ll lcm_xylcm(x,y);ll lcm_xzlcm(x,z);ll lcm_yzlcm(y,z);ll lcm_xyzlcm(lcm_xy,z);// 存储每个元素的各类步数索引单值/两两组合vectorplis_x,s_y,s_z;vectorplis_xy,s_xz,s_yz;// 存储单元素满足三者的步数仅存值下标由循环确定vectorlls_xyz(n,INF);// 遍历计算每个元素的所有步数核心公式无错保留for(inti0;in;i){ll numarr[i];// 单值步数(k - num%k) % k 确保num是k倍数时步数为0autocal[](ll k)-ll{if(k
return0;ll modnum%k;returnmod0?0:(k-mod);};ll sxcal(x),sycal(y),szcal(z);ll sxycal(lcm_xy),sxzcal(lcm_xz),syzcal(lcm_yz);ll sxyzcal(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_3INF;// 取前3个最小值即可枚举3*3*327次无性能损耗vectorplitop3_xget_top_k(s_x,
;vectorplitop3_yget_top_k(s_y,
;vectorplitop3_zget_top_k(s_z,
;// 枚举所有组合筛选索引互不相同的有效组合for(constautopx:top3_x){for(constautopy:top3_y){for(constautopz:top3_z){intixpx.second,iypy.second,izpz.second;// 三个索引互不相同且步数均为有效值if(ix!iyiy!izix!iz){min_3min(min_3,px.firstpy.firstpz.first);}}}}// 组合
两个不同元素一个满足两两一个满足单值 // 辅助函数计算「两两组合min 单值min」的最小有效和索引不同autocal_two[](constvectorplis_double,constvectorplis_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 resINF;// 索引不同直接相加if(min_double.second!min_single.second){resmin(res,min_double.firstmin_single.first);}else{// 索引相同找次小值要么换两两组合要么换单值ll sub_doubleget_min_exclude(s_double,min_single.second);ll sub_singleget_min_exclude(s_single,min_double.second);if(sub_double!INF)resmin(res,sub_doublemin_single.first);if(sub_single!INF)resmin(res,min_double.firstsub_single);}returnres;};ll min_2_xy_zcal_two(s_xy,s_z);// xy zll min_2_xz_ycal_two(s_xz,s_y);// xz yll min_2_yz_xcal_two(s_yz,s_x);// yz x// 组合5单个元素满足x、y、z ll min_1_xyzINF;for(ll val:s_xyz){min_1_xyzmin(min_1_xyz,val);}// 所有有效组合取最小值 ll ansINF;ansmin(ans,min_
;ansmin(ans,min_2_xy_z);ansmin(ans,min_2_xz_y);ansmin(ans,min_2_yz_x);ansmin(ans,min_1_xyz);coutansendl;return0;}
海角社区id:1120.7126,登陆入口-海角社区id:1120.7126,登陆入口应用
