贪心思想+排序+二分=好像会，但就是有点问题

解题思路:

首先，一定得把价格重新排序，然后就是买谁？肯定买价格高的先，因为价高的肯定不会是赠品啊，并且我选择了价格高的两件商品的话，我的赠品价格也是肯定不低的，所以从高位开始遍历。

其次，确定我选好了两件商品，在for里来一个计数器，累加到2表示凑齐两件商品，可以选赠品了。

赠品的选择在0到买的价格较低的商品之间，节约时间选择二分查找。

并且我一旦确定了赠品是谁，那么，下次选赠品就可以从0到上次二分的右指针-1之间找了。

为什么？

因为我选择买了价高的商品，我的赠品毋庸置疑也会是价格不低的。那么下一次，再买商品，买的价格都比之间的要低，赠品的价格也只会更低。

所以下一次二分，可以在上次二分右边界的左边进行。

最后：我写这道题花了一个下午。我之前在蓝桥云课写过一道题叫分巧克力。是国赛的贪心+二分。

也是用了很长时间才过的，我的问题在二分那块，关于left是小于right还是小于等于，一直不太清楚。

无法准确定位到我想要的数字的下标。（二分的难点）

借鉴了一位码友的代码，顿时云开见月明，为什么纠结最后返回是left还是right，我直接自己定义一个变量，来接满足我条件的值就好了。

注意事项:
选好赠品后，记得将计数器清0

二分里，res的初始值不能是0，因为会出现即使没进while里，第0件商品也会被记作赠品。

我这里没用状态数组，而是在价格数组上直接改的。因为价格都是>=1的，所以如果是赠品，就将价格置为-1也可以很好区分开。

参考代码:

import java.io.*;
import java.util.Arrays;

/**
 * @Author:杨雨彤
 * @date:2024/1/31 10:36
 */
public class Main {
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
    static  int n;
    static  int k;
    static long []ans;
    public static void main(String[]args) throws IOException {
        n=Integer.parseInt(br.readLine());
       ans=new long[n];
        String[] s = br.readLine().split(" ");
        for (int i = 0; i <n ; i++) {
            ans[i]=Long.parseLong(s[i]);
        }
        Arrays.sort(ans);
        long sum=0;
        int item=0;
        if(n>=3){
            k=n-3;//物品>=3才需要二分，且右边界初值是n-3
        }
        for (int i = n-1; i >=0; i--) {
             if(ans[i]==-1){//如果是赠品，跳，继续向前找
                 continue;
             }else{
                 sum+=ans[i];//不是赠品，一定会买
                 item++;//计数器
             }
             if(item==2){//买满两件商品
                 int index = getFree(i);
                 if(index>=0){
                     ans[index]=-1;//是赠品
                 }
                 item=0;//重新买
             }
        }
//        pw.println(Arrays.toString(ans));
        pw.println(sum);
        pw.flush();
        pw.close();
    }
    private  static  int getFree(int i){//二分查找，选赠品
        int left=0;
        int right=k;
        int res=-1;//记录最适合的赠品下标
        while(left<=right){
            int mid=(left+right)/2;
            if(ans[mid]*2<=ans[i]){
                  left=mid+1;
                  res=Math.max(res,mid);
            }else{
                right=mid-1;
            }
        }
        k=right-1;//right右侧不会再有赠品了
        return res;
    }
}