题目描述

本题贪心+二分不是最优解

贪心：通过分析我们可以发现，想要白嫖最大价值的物品，一定是先买两个价值大的物品。
对商品数组排序，枚举的时候，从后往前枚举，就可以选最大的

二分：先找 >= [(买1 + 买2)/2] + 1 的第一个位置,
那么左边的一个位置就是满足的[(a[i]) / 2]以内最大的

二分要注意的点：这里我们把r取到n,如果r=n了，说明没取到，返回-1

对于最后找到的位置应该是要>=0的，才能白嫖
int idx = find(v + 1) - 1 >= 0

贪心+二分

import java.util.*;

public class Main {

    static int n;
    static int N = 500010;

    static int[] a = new int[N];

    //标记数组 用来看是否已经白嫖
    static boolean[] st = new boolean[N];

    //先找 >= [(买1 + 买2)/2] + 1 的第一个位置
    public static int find(int target) {

        //这里我们把r取到n,如果r=n了，说明没取到，返回-1
        int l = 0, r = n;

        while (l < r) {
            int mid = (l + r) >> 1;
            //已经白嫖了
            if (st[mid]) {
                r = mid;//往左走
                continue;
            }
            if (a[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        //找不到返回-1
        return r == n ? -1 : r;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        long res = 0;

        //对商品数组排序，枚举的时候，从后往前枚举，就可以选最大的
        //跟截取字符串一样 最右边是取不到的
        Arrays.sort(a,0,n);

        //买了几个了
        int sum = 0;
        //每次买一个最大的
        for (int i = n - 1; i >= 0; i--) {
            //白嫖过了
            if (st[i]) {
                continue;
            }
            res += a[i];
            sum += 1;
            if (sum == 2) {
                sum = 0;
                int v = (a[i]) / 2;
                //先找 >= [(买1 + 买2)/2] + 1 的第一个位置, 左边的一个位置就是满足的[(a[i]) / 2]以内的
                int idx = find(v + 1) - 1;
                if (idx >= 0 && st[idx] == false) {
                    st[idx] = true;
                }
            }
        }

        System.out.println(res);
    }
}