炸鱼

炸鱼，网络流行语，原意指的是用炸药捕鱼。网络用语中，指拥有较高游戏水平的玩家，通过某些手段，长期恶意在低水平玩家群体中进行游戏的行为。
这鱼塘不好混啊

LCP 28. 采购方案

可怜的一道简单题，提交2万2，通过却只有4千8

先上自己无脑的题解吧

class Solution {
public:int purchasePlans(vector<int>& nums, int target) {sort(nums.begin(),nums.end());int num=0;for(int i=0; i<nums.size(); i++){int t=target-nums[i];for(int j=i+1; j<nums.size(); j++){if(nums[j]<=t) num++;num=num%1000000007;}}return num;}
};

哦这令人头大的双for啊！
超时了…

然后呢，还是想到了其他办法的
一个for套一个二分搜索，结果呢
把自己的盲点炸出来了，好家伙诶，这波不亏

自己想象可以解决问题的二分搜索

class Solution {
const long long MOD=1e9+7;
public:int purchasePlans(vector<int>& nums, int target) {sort(nums.begin(),nums.end());int size=nums.size();long long res=0;for(int i=0; i<size; i++){int left=i+1;int right=size;int t=target-nums[i];while(left<right){int mid=left+(right-left)/2;if(nums[mid]<t) left=mid+1;if(nums[mid]>t) right=mid-1;if(nums[mid-1]<=t&&t<nums[mid+1]) res+=(mid-left);}}return res%MOD;}
};

哦！瞧瞧这自以为是的if(nums[mid-1]<=t&&t<nums[mid+1]) res+=(mid-left);
自己想的是：找出小于或等于t的最后一个nums[mid]
但其实在二分搜索里，除了找寻某个数，还有就是找寻某一个搜索区间的左边界或右边界
而自己想的就是找到小于或等于t的区间的右边界

这里有一个传送门
详细讲解了二分搜索的细节问题和左右边界问题

---

而这道题用一个for和二分搜索的正确题解如下

class Solution {
const long long MOD=1e9+7;
public:int purchasePlans(vector<int>& nums, int target) {sort(nums.begin(),nums.end());int size=nums.size();long long res=0;for(int i=0; i<size; i++){int left=i+1;int right=size;int t=target-nums[i];while(left<right){int mid=left+(right-left)/2;if(nums[mid]==t) left=mid+1;if(nums[mid]<t) left=mid+1;if(nums[mid]>t) right=mid;}res+=(right-i-1);}return res%MOD;}
};

时间复杂度O(nlogn)
空间复杂度O(1)

这里有个函数upper_bound()

---

emmmm…
这还有个一看就会的题解方法——双指针

class Solution {
public:
const long long MOD = 1e9+7;int purchasePlans(vector<int>& nums, int target) {sort(nums.begin(),nums.end());int left=0;int right=nums.size()-1;long long ans=0;while(left<right){if(nums[left]+nums[right]>target) right--;else {ans+=(right-left);left++;}}return ans%MOD;}
};

不难吧，当时怎么就没想到呢？？？