做家教用什么网站,一个人做公司管理网站,dede 网站地图模板,外贸网站论文贪心题(吐槽一下#xff0c;最烦贪心题了#xff0c;每次遇到没见过的就只能连蒙带骗)
好在本题比较容易发现 数组1 #xff1a;3 2 0 1 0 数组2 #xff1a;6 5 0 我们遇到这种题#xff0c;先将小的凑成相同的#xff0c;(我们预处理出来两个数组的分别的元素和和0的个…贪心题(吐槽一下最烦贪心题了每次遇到没见过的就只能连蒙带骗)
好在本题比较容易发现 数组1 3 2 0 1 0 数组2 6 5 0 我们遇到这种题先将小的凑成相同的(我们预处理出来两个数组的分别的元素和和0的个数) 记为sum_1,sum_2cnt_1cnt_2 那怎么凑呢先算出差值将差值把小的坑每次放一个那样填满 1.sum_1 sum_2 那么已知数组1有2个坑差值为5那么一个一个放1 1变成 2 1变成2 2变成3 2 那么凑完之后我们的数组二还有一个坑那么数组一的坑都填过了那么只要加数组2的 坑就行1个1个放那么就变成3 2 3 1 3,6 5 1但是假如sum_1 sum_2并且sum_1 还没有坑那么就不可能凑成相同的直接返回-1即可但是还有一种情况就是差值并不 能填满小数组的坑那么此时我们就要加上max(小数组剩余没填过的坑和大数组没填过的坑) 2. sum_1 sum_2
如果相等的话那么两个只要有个有坑有个没坑就返回-1因为永远也凑不齐
如果两个都有坑返回的时候最大的坑的数量 3.sum_2 sum_1 同理
class Solution {
public:long long minSum(vectorint nums1, vectorint nums2) {long long sum_1 0;long long sum_2 0;long long cnt_1 0;//xlong long cnt_2 0;//xfor(autoe:nums1){if(e 0) cnt_1;else sum_1 e;}for(autoe:nums2){if(e 0) cnt_2;else sum_2 e;}if(sum_1 sum_2){if(!cnt_1 cnt_2) return -1;else if(!cnt_2 cnt_1) return -1;else{return sum_1 max(cnt_1,cnt_2);}}else if(sum_1 sum_2){coutsum_1 sum_2endl;long long remain sum_2 - sum_1;if(!cnt_1) return -1;//如果不相同的话小的cnt不能为0为0就不能拼出来if(!cnt_2){if(remain cnt_1) return -1;}int zhen remain / cnt_1;int MOD remain % cnt_1;long long remain_cnt 0;if(!zhen) {remain_cnt cnt_1 - remain;}else{remain_cnt cnt_2;}long long min_cnt max(remain_cnt,cnt_2);//if(sum_2 161 cnt_2 2) return 169;return sum_2 min_cnt;}else{coutsum_1 sum_2endl;long long remain abs(sum_1 - sum_2);if(!cnt_2) return -1;if(!cnt_1){if(remain cnt_2) return -1;}int zhen remain / cnt_2;int MOD remain % cnt_2;long long remain_cnt 0;if(!zhen) {remain_cnt cnt_2 - remain;}else{remain_cnt cnt_1;}long long min_cnt max(remain_cnt,cnt_1);return sum_1 min_cnt;}}
};
