寻亲网站开发设计文档,河南洛阳网站建设,学院网站建设项目范围变更申请表,石家庄市建设局网站信息公开LCP 28 采购方案
1.题目
小力将 N 个零件的报价存于数组 nums。小力预算为 target#xff0c;假定小力仅购买两个零件#xff0c;要求购买零件的花费不超过预算#xff0c;请问他有多少种采购方案。
注意#xff1a;答案需要以 1e9 7 (1000000007) 为底取模#xff0c…LCP 28 采购方案
1.题目
小力将 N 个零件的报价存于数组 nums。小力预算为 target假定小力仅购买两个零件要求购买零件的花费不超过预算请问他有多少种采购方案。
注意答案需要以 1e9 7 (1000000007) 为底取模如计算初始结果为1000000008请返回 1
2.解题思路
从题目给的注意和数据量来看暴力循环一定是不行的。因此代替暴力循环最常见的方法就是双指针。
首先分析题目输入是数组和预算目标值。输出的是数组中任意选取两个数相加可以小于目标值的所有方案。因此很容易想到需要对数组做一次排序。
step1. 数组升序排序qsort
step2. 设置左指针在有序数组左端右指针在有序数组右端
step3. 以左指针为外循环基准左移右指针。当左指针 右指针的值恰好小于目标值时从左指针到右指针之间的所有数据则都满足要求则统计完当前左指针下满足条件的方案。
step4. 然后右移一次左指针右指针在当前位置下积蓄左移重复step3统计累计所有方案这时右指针不需要从最右端重新再刷新了因为左指针向右移动后一定满足 nums[left] nums[right] nums[left 1] nums[right]
step5. 结束条件当左指针和右指针相遇以后左右指针之间的数据量为负数则不符合常理退出循环。
3.数据结构与算法
算法排序算法双指针
4.排序算法 双指针
int sort_up(const void *a, const void *b) {return *(int *)a - *(int *)b;
}
int purchasePlans(int* nums, int numsSize, int target){qsort(nums, numsSize, sizeof(nums[0]), sort_up);int left 0;int right numsSize - 1;long long sum 0;while (left right) {if (nums[right] nums[left] target)right--;else {sum (long long)(right - left);left;c}}sum (int) (sum % (1000000007));return sum;
}
