题目描述

某商场有 Ⅳ 件商品，其中第之件的价格是Ai。现在该商场正在进行“买二赠一”的优惠活动，具体规则是:每购买2件商品，假设其中较便宜的价格是 P(如果两件商品价格一样，则 P等于其中一件商品的价格)，就可以从剩余商品中任选一件价格不超过P/2的商品，免费获得这一件商品。可以通过反复购买 2件商品来获得多件免费商品，但是每件商品只能被购买或免费获得一次。小明想知道如果要拿下所有商品(包含购买和免费获得)，至少要花费多少钱?

样例

输入样例：
7
1 4 2 8 5 7 1
输出样例：
25

算法1

(Java贪心+二分)

最后一个样例过不了，显然贪心并非最优解。

不过还是想分享一下，之前遇到这类题总是远远地看，就算有想法也不能动手实现。在敲了几天，也看了不少大佬的代码，似乎自己成长了一点。学会一些简单的思路了，比如想到这道题贪心实现，二分优化时间复杂度。
对于二分的第一个值，还是最后一个值的问题。我又研究了一番，明白了如何合理缩区间，也就是向所需答案逼近。
分享一个很喜欢的话，“怕什么真理无穷，进一寸有一寸的欢喜”，慢慢来，越来越好！

时间复杂度

O(nlogn)

Java 代码

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

public class Main {
    static int n;
    static long[] a=new long[1000010];
    static long[] flag=new long[1000010];
    static boolean finishFree=false;
    static int flagCount=0;
    static void findFree(long p) {
//      System.out.println("p为："+p);
        int l=0,r=n-1;
        p=p>>1;
//      System.out.println("p/2为："+p);
        while(l<r) {
            int mid=l+r+1>>1;
            if(flag[mid]==1) {
                r=mid-1;
                continue;
            }
            if(a[mid]<=p) {
                l=mid;
            }else {
                r=mid-1;
            }           
        }
        if(a[l]>p) {
//          System.out.println("找不到低于p/2的商品，无法赠送");
            finishFree=true;
            return;
        }else {
            flag[l]=1;
            flagCount++;
//          System.out.println("免费获得了价格为："+a[l]+"的商品");
        }

    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader inReader=new BufferedReader(new InputStreamReader(System.in));
        n=Integer.parseInt(inReader.readLine());
        String[] str=inReader.readLine().split(" ");
        for(int i=0;i<n;i++) {
            a[i]=Long.parseLong(str[i]);
        }
        Arrays.sort(a,0,n);

        long priceTotal=0;
        int freeChance=0;
        long minPrice=Long.MAX_VALUE;
        for(int i=n-1;i>=0;i--) {
            if(flag[i]!=1) {
                priceTotal+=a[i];
//              System.out.println("购买了价格为： "+a[i]+"的商品");
                minPrice=Math.min(minPrice, a[i]);
                freeChance++;
                flagCount++;
            }
            if(freeChance==2&&!finishFree) {
//              System.out.println("进入免费赠送环节");
                findFree(minPrice);
                minPrice=Long.MAX_VALUE;
                freeChance=0;
            }
            if(flagCount==n) {
                break;
            }
        }
        System.out.println(priceTotal);
    }
}