P1873 砍树（二分答案）

Dear 丶 2022-11-10 14:20 127阅读 0赞

[传送][Link 1]

这是个高精度的题，如何暴力枚举，会爆炸，用了一次二分和一次枚举，时间复杂度是 O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))

对于n是有符号的情况下，当可以保证 n > 0 n>0 n>0， n > > 1 n>>1 n>>1比 n / 2 n/2 n/2指令数更少。

#include<bits/stdc++.h>
    #define ll long long
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    #define fep(i,a,b) for(int i=b;i>=a;--i)
    #define scf(x) scanf("%lld",&x)
    #define prf(x) printf("%lld\n",x)
    #define deprf(x) printf("[%lld]\n",x)
    #define mem(x,y) memset(x,y,sizeof(x))
    #define inf 2147483647
    const int mod=1e9+7;
    const int maxn=1e6;
    using namespace std;
    ll a[maxn+5];
    
    int n;
    ll m;
    ll check(ll k){ 
        ll sum = 0;
        rep(i,1,n){ 
            if(a[i]>k)
                sum += a[i]-k;
        }
        return sum >= m;
    }
    
    ll f(){ 
        int l = 1, r = maxn+1;
        while(l+1 < r){ 
            ll mid = (l+r) >> 1;
            if(check(mid))
                l = mid;
            else
                r = mid;
        }
        cout <<  l;
    }
    int main()
    { 
        cin >> n >> m;
        rep(i,1,n)
            cin >> a[i];
        f();
        return 0;
    }

[Link 1]: https://www.luogu.com.cn/problem/P1873

发表评论取消回复

表情：

评论列表（有 0 条评论，127人围观）

还没有评论，来说两句吧...

相关阅读

相关二分答案总结

二分的三种实现形式： 1.最普通的： while(l<=r){ int mid=l+r>>1; if(check(m

曾经终败给现在/ 2024年03月30日 09:30/ 0 赞/ 78 阅读

相关二分搜索树

一、概念及其介绍二分搜索树（英语：Binary Search Tree），也称为二叉查找树、二叉搜索树、有序二叉树或排序二叉树。满足以下几个条件：若它的

墨蓝/ 2024年03月16日 20:54/ 0 赞/ 82 阅读

相关【树上差分+LCA】篮球杯砍树

省赛的题现在来补感觉什么都不会，已经要没了题意： ![1ffcc3d937d549809ffd88f0082c96cc.png][] 思路：考虑一条边，两端有两

港控/mmm°/ 2024年03月16日 09:29/ 0 赞/ 59 阅读

相关 Java实现洛谷 P1873 砍树（StreamTokenizer+IO+二分）

P1873 砍树 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ib

我就是我/ 2023年07月21日 11:14/ 0 赞/ 11 阅读

相关巨斧砍大树

巨斧砍大树 Description 阿福最近练就了一个新的招式：巨斧砍大树。这个招式可以砍掉一颗二叉搜索树的某个子树。现在，阿福面前有一颗 nn 个结点的二叉搜索树，

本是古典何须时尚/ 2022年12月21日 15:58/ 0 赞/ 106 阅读

相关 P1873 砍树（二分答案）

[传送][Link 1] 这是个高精度的题，如何暴力枚举，会爆炸，用了一次二分和一次枚举，时间复杂度是 O ( n l o g ( n ) ) O(nlog(n)) O(nl

Dear 丶/ 2022年11月10日 14:20/ 0 赞/ 128 阅读

相关 675 为高尔夫比赛砍树（宽搜）

1. 问题描述：你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示，在这个矩阵中： 0 表示障碍，无法触碰 1 表示地面，可以行走

淩亂°似流年/ 2022年09月02日 13:45/ 0 赞/ 103 阅读

相关 P3957 跳房子[二分答案][dp][单调队列]

P3957 跳房子前年pj没去年难好吧首先要发现这个答案是有单调性的。这个很显然了：氪金越多游戏越容易玩，氪金越少越难。然而也有界限：如果所有正数的和加起来

朱雀/ 2021年12月22日 15:52/ 0 赞/ 220 阅读

相关 [二分][主席树] Luogu P2839 Middle

题目描述一个长度为n的序列a，设其排过序之后为b，其中位数定义为b\[n/2\]，其中a,b从0开始标号,除法取下整。给你一个长度为n的序列s。回答Q个这样的询

向右看齐/ 2021年12月03日 22:51/ 0 赞/ 271 阅读

相关二分答案学习笔记

内容先![1660941-20190626085335054-1727597896.png][] 等我多做些题在来写转载于:https://www.cnblogs.c

谁践踏了优雅/ 2021年11月02日 09:16/ 0 赞/ 398 阅读