专栏首页机器学习入门挑战程序竞赛系列(23):3.2折半枚举

挑战程序竞赛系列(23):3.2折半枚举

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/73897070

挑战程序竞赛系列(23):3.2折半枚举

详细代码可以fork下Github上leetcode项目,不定期更新。

练习题如下:

POJ 2785: 4 Values whose Sum is 0

基本想法: 全部枚举,判断sum == 0,时间复杂度为O(n4)O(n^4),优化,折半枚举。

确定sum意味着给定两个组合,另外一半也将确定,所以可以给出任意两个元素的所有组合,进行折半搜索。sum = a + b,a确定b跟着确定,这是折半的核心思想。这样b的搜索可以采用二分。

总的来说,sum并不关系每个独立的个体具体是什么值,它只关心总和是否等于算,所以sum = a + b + c + d和sum = (a + b) + (c + d),对于sum来说没有区别。既然无区别,干嘛要用独立性如此高的算法O(n4)O(n^4)来实现呢?

当(a + b)看成整体后,它的搜索成本自然就下去了。

代码如下:

    void solve() {
        int n = ni();
        int[] A = new int[n];
        int[] B = new int[n];
        int[] C = new int[n];
        int[] D = new int[n];
        for (int i = 0; i < n; ++i){
            A[i] = ni();
            B[i] = ni();
            C[i] = ni();
            D[i] = ni();
        }

        int[] arra = new int[n * n];
        for (int i = 0, k = 0; i < n; ++i){
            for (int j = 0; j < n; ++j){
                arra[k++] = C[i] + D[j];
            }
        }
        Arrays.sort(arra);

        long cnt = 0;
        for (int i = 0; i < n; ++i){
            for (int j = 0; j < n; ++j){
                int key = -(A[i] + B[j]);
                int lo = lowBound(arra, key);
                int hi = upBound(arra, key);
                if (lo == -1 || hi == -1) continue;
                cnt += (hi - lo + 1);
            }
        }
        out.println(cnt);
    }

    private int lowBound(int[] arra, int key){
        int lf = 0, rt = arra.length - 1;
        while (lf < rt){
            int mid = lf + (rt - lf) / 2;
            if (arra[mid] < key) lf = mid + 1;
            else rt = mid;
        }
        if (arra[rt] == key) return rt;
        return -1;
    }

    private int upBound(int[] arra, int key){
        int lf = 0, rt = arra.length - 1;
        while (lf < rt){
            int mid = lf + (rt - lf + 1) / 2;
            if (arra[mid] > key) rt = mid - 1;
            else lf = mid;
        }
        if (arra[lf] == key) return lf;
        return -1;
    }

POJ 3977: Subsets

全部枚举需要O(2n)O(2^n)次方,OJ不让过,所以可以采用折半的思路,此题和上题相似,无非由于子集的个数不确定,所以有sum = a + b + c …这种情况,且sum不是固定的值,而是尽可能接近0,天啊噜,改了20多次,依旧WA。

思路: 对数据进行划分,分成n/2和n - n/2的两个子集,分别对子集中的所有可能组合枚举,分别得到两个sum1和sum2,令sum1 + sum2尽可能的接近0,所以只要针对某个sum集合进行排序,二分。

  • 用二分法逼近答案,因为可能会有多解的情况
  • 所以需要进行两次,第一次寻找最接近0的负值,第二次寻找最接近0的正值。
  • 然后扫描这两者之间的所有元素,找出sum最小,且count最小的组合

自己代码如下:

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            int n = new Integer(br.readLine());
            if (n == 0) break;
            long[] arra = new long[n];

            String input[] = br.readLine().split("\\s");
            for (int i = 0; i < n; i++) {
                arra[i] = new Long(input[i]);
            }

            long[] LL = new long[n];
            long[] RR = new long[n];
            int LN = 0, RN = 0;

            for (int i = 0; i < n; i += 2) {
                LL[LN++] = arra[i];
                if (i + 1 < n)
                    RR[RN++] = arra[i + 1];
            }

            if (RN == 0) {
                System.out.println(LL[0] + " " + 1);
                continue;
            }

            Sum[] sums = new Sum[1 << RN];
            for (int i = 0; i < 1 << RN; ++i) {
                long sum = 0;
                int cnt = 0;
                for (int j = 0; j < RN; ++j) {
                    if ((i & (1 << j)) != 0) {
                        sum += RR[j];
                        cnt++;
                    }
                }
                sums[i] = new Sum(sum, cnt);
            }
            Arrays.sort(sums);

            long ans = 1000000000000001l;
            int ansc = 36;
            for (int i = 0; i < 1 << LN; ++i) {
                long key = 0;
                int cnt = 0;
                for (int j = 0; j < LN; ++j) {
                    if ((i & (1 << j)) != 0) {
                        key += LL[j];
                        cnt++;
                    }
                }

                int l = 0;
                int r = sums.length;
                while (r - l > 1) {
                    int m = (l + r) / 2;
                    if (sums[m].sum + key >= 0) {
                        r = m;
                    } else {
                        l = m;
                    }
                }
                int L = l;
                l = -1;
                r = sums.length - 1;
                while (r - l > 1) {
                    int m = (l + r) / 2;
                    if (sums[m].sum + key > 0) {
                        r = m;
                    } else {
                        l = m;
                    }
                }
                int R = r;
                for(int k = L; k <= R; ++k){
                    long tempsum = Math.abs(sums[k].sum + key);
                    int tempcount = sums[k].cnt + cnt;
                    if (tempcount == 0) continue;

                    if(tempsum < ans){
                        ans = tempsum;
                        ansc = tempcount;
                    }
                    else if(tempsum == ans & tempcount < ansc){
                        ansc = tempcount;
                    }
                }
            }
            System.out.println(ans + " " + ansc);
        }
    }

WA到心碎,正确代码可以参考http://poj.org/showmessage?message_id=346495

POJ 2549: Sumsets

思路: a + b = d - c,所以把等式两边表示出来用个二分就解决了,一开始二分(a+b),但枚举(d-c)需要的次数较大,所以二分(d-c),枚举(a+b),此时只需要n⋅(n−1)/2n \cdot (n - 1) / 2次的二分查询,勉强过了。前者TLE了。

代码如下:

    void solve() {
        while (true){
            int n = ni();
            if (n == 0) break;
            long[] arra = new long[n];
            Map<Long, Integer> map = new HashMap<Long, Integer>();
            for (int i = 0; i < n; ++i){
                arra[i] = nl();
                if (!map.containsKey(arra[i])){
                    map.put(arra[i], 0);
                }
                map.put(arra[i], map.get(arra[i]) + 1);
            }

            TwoSum[] sums = new TwoSum[n * n];
            for (int i = 0; i < sums.length; ++i){
                sums[i] = new TwoSum(Long.MAX_VALUE, -1, -1);
            }

            int N = 0;
            for (int i = 0; i < n; ++i){
                if (map.get(arra[i]) != 1) continue;
                for (int j = 0; j < n; ++j){
                    if (i == j) continue;
                    sums[N++] = new TwoSum(arra[i] - arra[j], i, j);
                }
            }
            Arrays.sort(sums);
            long max = Long.MIN_VALUE;

            for (int i = 0; i < n; ++i){
                for (int j = i + 1; j < n; ++j){
                    long key = arra[i] + arra[j];
                    int lo = loBound(sums, N, key);
                    int hi = upBound(sums, N, key);
                    if (lo == -1 || hi == -1) continue;
                    for (int l = lo; l <= hi; ++l){
                        TwoSum sum = sums[l];
                        if (sum.i == i || sum.j == i || sum.i ==j || sum.j == j) continue;
                        max = Math.max(arra[sum.i], max);
                    }
                }
            }

            if (max == Long.MIN_VALUE) out.println("no solution");
            else out.println(max);

        }
    }

    public int upBound(TwoSum[] sums, int len, long key){
        int lf = 0, rt = len - 1;
        while (lf < rt){
            int mid = lf + (rt - lf + 1) / 2;
            if (sums[mid].sum > key) rt = mid - 1;
            else lf = mid;
        }
        if (sums[lf].sum == key) return lf;
        return -1;
    }

    public int loBound(TwoSum[] sums, int len, long key){
        int lf = 0, rt = len - 1;
        while (lf < rt){
            int mid = lf + (rt - lf) / 2;
            if (sums[mid].sum < key) lf = mid + 1;
            else rt = mid;
        }
        if (sums[rt].sum == key) return rt;
        return -1;
    }

    class TwoSum implements Comparable<TwoSum>{
        long sum;
        int i;
        int j;

        public TwoSum(long sum, int i, int j) {
            this.sum = sum;
            this.i = i;
            this.j = j;
        }

        @Override
        public String toString() {
            return "" + sum;
        }

        @Override
        public int compareTo(TwoSum o) {
            return this.sum < o.sum ? -1 : 1;
        }
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • K-th Smallest Prime Fraction

    思路1: 一种聪明的做法,如果A = [1, 7, 23, 29, 47],那么有:

    用户1147447
  • 挑战程序竞赛系列(36):3.3线段树和平方分割

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 挑战程序竞赛系列(32):4.5 A*与IDA*

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • LeetCode 323. 无向图中连通分量的数目(并查集)

    给定编号从 0 到 n-1 的 n 个节点和一个无向边列表(每条边都是一对节点),请编写一个函数来计算无向图中连通分量的数目。

    Michael阿明
  • 树上莫队算法

    attack
  • 2017.5.20欢(bei)乐(ju)赛解题报告

    预计分数:100+20+50=first 实际分数:20+0+10=gg 水灾(sliker.cpp/c/pas) 1000MS  64MB 大雨应经下了几天雨...

    attack
  • BZOJ3143: [Hnoi2013]游走(期望DP 高斯消元)

    Description 一个无向连通图,顶点从1编号到N,边从1编号到M。  小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当...

    attack
  • OpenCV图像处理专栏十 | 利用中值滤波进行去雾

    这是OpenCV图像处理专栏的第十篇文章,介绍一种利用中值滤波来实现去雾的算法。这个方法发表于国内的一篇论文,链接我放附录了。

    BBuf
  • 1077: 输入入门(2)

    描述:计算A+B 输入:输入第1行为一个整数n(1≤n≤10),代表测试的组数。下面有n组测试数据,每组1行,为2个整数,为A, B。 输出:输出A+B的值...

    bboysoul
  • 排序算法——一篇文章搞懂常用的排序算法

    排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。 稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记...

    海盗船长

扫码关注云+社区

领取腾讯云代金券