LCP 28 采購方案

1.題目

小力將 N 個(gè)零件的報(bào)價(jià)存于數(shù)組 nums。小力預(yù)算為 target，假定小力僅購買兩個(gè)零件，要求購買零件的花費(fèi)不超過預(yù)算，請問他有多少種采購方案。

注意：答案需要以 1e9 + 7 (1000000007) 為底取模，如：計(jì)算初始結(jié)果為：1000000008，請返回 1

2.解題思路

從題目給的注意和數(shù)據(jù)量來看，暴力循環(huán)一定是不行的。因此代替暴力循環(huán)最常見的方法就是雙指針。

首先分析題目：輸入是數(shù)組和預(yù)算目標(biāo)值。輸出的是數(shù)組中任意選取兩個(gè)數(shù)相加可以小于目標(biāo)值的所有方案。因此很容易想到需要對數(shù)組做一次排序。

step1. 數(shù)組升序排序（qsort）

step2. 設(shè)置左指針在有序數(shù)組左端，右指針在有序數(shù)組右端

step3. 以左指針為外循環(huán)基準(zhǔn)，左移右指針。當(dāng)左指針 + 右指針的值恰好小于目標(biāo)值時(shí)，從左指針到右指針之間的所有數(shù)據(jù)則都滿足要求，則統(tǒng)計(jì)完當(dāng)前左指針下，滿足條件的方案。

step4. 然后右移一次左指針，右指針在當(dāng)前位置下積蓄左移，重復(fù)step3統(tǒng)計(jì)累計(jì)所有方案（這時(shí)，右指針不需要從最右端重新再刷新了，因?yàn)樽笾羔樝蛴乙苿?dòng)后，一定滿足 nums[left] + nums[right] <= nums[left + 1] + nums[right]）

step5. 結(jié)束條件：當(dāng)左指針和右指針相遇以后，左右指針之間的數(shù)據(jù)量為負(fù)數(shù)，則不符合常理，退出循環(huán)。

3.數(shù)據(jù)結(jié)構(gòu)與算法

算法：排序算法+雙指針

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; }

總結(jié)

以上是生活随笔為你收集整理的[LCP28] 采购方案的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。