网站建设的几个要素,企业标准官网入口,企业网站销售,seo发展现状链接#xff1a;
2366. 将数组排序的最少替换次数
题意#xff1a;
一个正整数数组nums#xff0c;每次操作可以将一个数字拆分成两个数字#xff08;CAB#xff09;#xff0c;然后放回原来的位置#xff08;XCXXABX或XBAX#xff09;#xff0c;求将这个…链接
2366. 将数组排序的最少替换次数
题意
一个正整数数组nums每次操作可以将一个数字拆分成两个数字CAB然后放回原来的位置XCXXABX或XBAX求将这个数组变成非递减数组的最少操作次数
解
连摇三题困难真是蚌埠住了前两题写不出来本来这题也想要摇掉了看了一眼这题标签是个贪心又瞄了一眼提示搞一哈
首先最后一个数字不应该拆因为要非递减最后数字越大越好然后就是平均分可以保留更大的数字
然后从后往前遍历如果这个数字(now)比后面这个数字(after)大则我要拆分同时拆分时要保留最大的数字则用now/after计算拆分的组数注意当now%after0结果需要加一同时将拆分组数-1需要次数加入答案然后将now拆为now/f
比如21 7可知拆分为3个7但是15 7也是拆分3组(15//71)一组就是5(平均分保留最大的数字)
实际代码
#includebits/stdc.h
using namespace std;
long long minimumReplacement(vectorint nums)
{long long int ans0;if(nums.size()1) return 0;auto itnums.rbegin();for(int after*it;it!nums.rend();it){int now*it;if(nowafter){int fnow/after;if(now%after) f;ans(f-1);*itnow/f;//coutfendl;}after*it;}return ans;
}
int main()
{vectorint nums;int temp;coutCtrl Z to input EOFendl;while(cintemp){nums.push_back(temp);}int ansminimumReplacement(nums);coutansendl;return 0;
}限制
1 nums.length 1051 nums[i] 109
