2576. 求出最多标记下标（24.9.12）

说明

由于电脑坏了，断更了几日，力扣每日一题从今日开始恢复日更。

题目

给你一个下标从 0 开始的整数数组 nums。

• 一开始，所有下标都没有被标记。你可以执行以下操作任意次：

选择两个互不相同且未标记的下标 i 和 j，满足 2 * nums[i] <= nums[j]，标记下标 i 和 j。

要求返回 nums 中最多可以标记的下标数目。

示例 1

输入：nums=[3,5,2,4]
输出：2
解释：第一次操作中，选择 i=2 和 j=1，操作可以执行的原因是 2*nums[2]<=nums[1]，标记下标 2 和 1。没有其他更多可执行的操作，所以答案为 2。

示例 2

输入：nums=[9,2,5,4]
输出：4
解释：第一次操作中，选择 i=3 和 j=0，操作可以执行的原因是 2*nums[3]<=nums[0]，标记下标 3 和 0。第二次操作中，选择 i=1 和 j=2，操作可以执行的原因是 2*nums[1]<=nums[2]，标记下标 1 和 2。没有其他更多可执行的操作，所以答案为 4。

示例 3

输入：nums =[7,6,8]
输出：0
解释：没有任何可以执行的操作，所以答案为 0。

提示

1. 1 <= nums.length <= 10^5；
2. 1 <= nums[i] <= 10^9。

解题思路

见代码

代码

class Solution {
public:
    int maxNumOfMarkedIndices(vector<int>& nums) {
        int n=nums.size();
        sort(nums.begin(),nums.end());
        /*
        假设我们的答案是 mid，
        那么我们则需要保证我们的第 i 小的数字（设为 x ） 与倒数第 mid大的数（设为 y）存在如下关系，
        x*2<=y
        因此我们通过排序，来维持第 i 小的数我的位置和倒数第 mid 大的数，同样这样只需要通过访问下表达到算法的优化
        */
        //根据上述推论来写一个判断
        auto check=[&](int k)->bool{
            //假设答案为k组，那么说明存在k组，因此只需要遍历0~k
            for(int i=0;i<k;i++){
                if(nums[i]*2>nums[n-k+i]) return false;
            }
            return true;
        };
        //二分的答案左右端点判断
        //假设 有 n 个数
        //二分的左端点为0，因为其最小值为0；
        //二分的右端点为 n/2，因为答案必须是互补相同且未标记的，假设每个数字都被选中，那么答案就为 n/2
        int l=0,r=n/2;
        while(l<r){
            int mid=(l+r+1)/2;
            if(check(mid)){
                //成立，则说明有可能存在或者有更多的组数
                l=mid;
            }
            else{
                //不成立，则说明组数太多了
                r=mid-1;
            }
        }
        return l*2;//每组为一对的(i,j)，因此答案数为对数*2
    }
};