专栏首页机器学习入门挑战程序竞赛系列(16):3.1最大化最小值

挑战程序竞赛系列(16):3.1最大化最小值

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

挑战程序竞赛系列(16):3.1最大化最小值

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

练习题如下:

花了两个月,刷完了初级篇,算入门了,心累。

POJ 3258: River Hopscotch

思路:属于二分,可以看作f(d)f(d)的一个函数,表示当前距离下,移除的石头,d越大,移除的石头也就越多。很明显是一种有序结构,所以直接在解空间中搜索满足条件的最小d即可。

static int[] rocks;
    static int N;
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        int L = in.nextInt();
        N = in.nextInt();
        int M = in.nextInt();
        rocks = new int[N + 2];
        rocks[0] = 0;
        for (int i = 1; i <= N; ++i){
            rocks[i] = in.nextInt();
        }
        rocks[N+1] = L;
        Arrays.sort(rocks);
        lf = 0;
        rt = L;
        System.out.println(binarySearch(M));
    }

    static int lf;
    static int rt;
    public static int binarySearch(int M){
        while (lf < rt){
            int mid = lf + (rt - lf + 1) / 2;
            if (remove(mid) > M) rt = mid - 1;
            else lf = mid;
        }
        if (remove(lf) <= M) return lf;
        return 0;
    }

    public static int remove(int d){
        int cnt = 0;
        for (int i = 1, j = 0; i <= N + 1; ++i){
            if (rocks[i] - rocks[j] < d){
                cnt++;
            }else{
                j = i;
            }
        }
        return cnt;
    }

POJ 3273: Monthly Expense

思路:二分就不用说了,主要是f(m)f(m)函数,给定一个金钱范围,尽可能的塞满,问最多能塞出多少个桶。

代码如下:

static int N;
    static int M;
    static int[] money;

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();
        money = new int[N];

        int max = 0;
        int sum = 0;
        for (int i = 0; i < N; ++i){
            money[i] = in.nextInt();
            max = Math.max(max, money[i]);
            sum += money[i];
        }

        int lf = max;
        int rt = sum;

        while (lf < rt){
            int mid = lf + (rt - lf) / 2;
            if (valid(mid) > M) lf = mid + 1;
            else rt = mid;
        }
        if (valid(lf) <= M) System.out.println(lf);
        else System.out.println(0);
    }

    public static int valid(int m){
        int cnt = 0;
        int sum = 0;
        for (int i = 0; i < N; ++i){
            sum += money[i];
            if (sum == m){
                sum = 0;
                cnt++;
            }
            else if (sum > m){
                sum = money[i];
                cnt++;
            }
        }
        if (sum != 0) cnt++;
        return cnt;
    }

POJ 3104: Drying

思路: 采用模拟,专注用最优策略,每次选择最湿的衣服用散热器,其余衣服减一,用优先队列保持当前最湿。

代码如下:

public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] clothes = new int[N];
        MaxPQ<Integer> pq = new MaxPQ<Integer>();
        for (int i = 0; i < N; ++i){
            clothes[i] = in.nextInt();
            pq.insert(clothes[i]);
        }
        int K = in.nextInt();
        int cnt = 0;
        while (!pq.isEmpty()){
            List<Integer> tmp = new ArrayList<Integer>();
            int c = pq.delMax();
            c -= K;
            if (c > 0) tmp.add(c);
            int size = pq.size();
            for (int i = 0; i < size; ++i){
                c = pq.delMax();
                c--;
                if (c > 0) tmp.add(c);
            }
            for (int t : tmp) pq.insert(t);
            cnt++;
        }
        System.out.println(cnt);
    }

TLE了,看来一定有数学性质来简化这过程。刚才的过程考虑了最优策略,而且程序的执行很navie,一步步走,或者你可以认为是单线程的(这也是为什么模拟慢的原因)。

所以优化的思路是能否利用一些数学性质来加快运算速度?脑子里蹦出来一个并发的概念,但必须符合并发才行啊,在哪里?此处只有一个地方有并发,每分钟自然风干时,所有的衣服都会自减一,思路就在这。而用散热器风干时,每个时刻只能操作一次,这意味着需要用散热器风干时,它就必须单独算一次。(计数是串行的)

所以优化思路是:减去所有衣服自然风干的状态(意味着模拟一下子被简化),计算剩余湿度需要散热器的次数。(而一件衣服的计数也可以在O(1)O(1)的操作内得到)

k⋅x+(mid−x)≥ai

k \cdot x + (mid - x) \ge a_i

得:

x≥⌈ai−midk−1⌉

x \ge \lceil \frac{a_i - mid}{k -1}\rceil

有趣的是,这道题如果不去假设某个mid存在,直接采用模拟很难在有限的时间内解决。而上述公式告诉我们一个事实,mid与x之间存在着映射关系,且符合有序,所以直接用二分搜索解空间就好。

代码如下:

static int[] clothes;
    static int K;
    static int N;
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        clothes = new int[N];
        int max = 0;
        for (int i = 0; i < N; ++i){
            clothes[i] = in.nextInt();
            max = Math.max(max, clothes[i]);
        }
        K = in.nextInt();
        if (K == 1){
            System.out.println(max);
            return;
        }
        int lf = 0;
        int rt = max;
        while (lf < rt){
            int mid = lf + (rt - lf) / 2;
            if (!valid(mid)) lf = mid + 1;
            else rt = mid;
        }
        System.out.println(lf);
    }

    public static boolean valid(int m){
        for (int i = 0, times = 0; i < N; ++i){
            int more = clothes[i] - m;
            if (more >= 0){
                times += (int) Math.ceil(more / (1.0 * (K - 1)));
                if (times > m) return false;
            }
        }
        return true;
    }

POJ 3045: Cow Acrobats

和二分没什么关系。。。可以直接求解,关键是需要证明一下。每次把力量和重量总和最大的放在最下面就好了。

证明:(反证法)

假设把力量和重量总和较小的牛放在最下面,那么它的risk一定比力量和重量综合最大的risk大。

所以,我们要确保的是,放入【力重总和】最大的那头牛后,剩余的可能risk都小于较小那头的risk。

还是画个图吧。

所以我们有理由选择最大的,而不是较小的,毕竟最大的能够保证risk较小,且经后的risk都小于等于risk2,接着我们采用归纳即可,最大的选择完毕,意味着剩余的元素是个子问题,继续选择次大的即可。(隐含着选择最大后,必须选择次大元素,而非其他元素的一个过程)

代码如下:

static class Cow implements Comparable<Cow>{
        int weight;
        int strength;
        public Cow(int weight, int strength){
            this.weight = weight;
            this.strength = strength;
        }

        @Override
        public int compareTo(Cow o) {
            return (o.weight + o.strength) - (this.weight + this.strength);
        }
    }

    static Cow[] cows;
    static int N;
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        cows = new Cow[N];
        long sum = 0;
        for(int i = 0; i < N; ++i){
            int w = in.nextInt();
            int s = in.nextInt();
            cows[i] = new Cow(w, s);
            sum += cows[i].weight;
        }
        Arrays.sort(cows);
        long risk = Integer.MIN_VALUE;
        for (int i = 0; i < N; ++i){
            sum -= cows[i].weight;
            risk = Math.max(risk, sum - cows[i].strength);
        }
        System.out.println(risk);
    }

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 挑战程序竞赛系列(26):3.5二分图匹配(1)

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

    用户1147447
  • 挑战程序竞赛系列(21):3.2反转

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

    用户1147447
  • 挑战程序竞赛系列(19):3.1最小化第k大的值

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

    用户1147447
  • 杭电1003--动态规划

    思路:用数组a[]记录序列中的数,对于a[i]只有两种可能 1.为一个序列的首2.为一个序列的尾。 用数组b[i]记录以第i个数结尾的序列的最大和,则 b[...

    杨鹏伟
  • HDU 1867(kmp应用)

    Generally speaking, there are a lot of problems about strings processing. Now yo...

    dejavu1zz
  • 1062. 最简分数(20)

    一个分数一般写成两个整数相除的形式:N/M,其中M不为0。最简分数是指分子和分母没有公约数的分数表示形式。

    AI那点小事
  • hdu1005

    @坤的
  • Top K问题

    如果你对上述两者的原理有所了解,可以继续往下看.如果不了解,可以点击链接先看一下基础~.

    呼延十
  • E - Explorer

    给你 n 个点,m 条边,每条边给你一组数 (u, v, l, r) 代表如果你想从u点走到v点,你的身高需要满足范围 [ l , r ] ,问你从 1 走到...

    用户2965768
  • BZOJ2705: [SDOI2012]Longge的问题(欧拉函数)

    \(ans = \sum_{d | n} d \phi(\frac{n}{d})\)

    attack

扫码关注云+社区

领取腾讯云代金券