首页 > 其他分享 >二分

二分

时间：2024-05-22 20:08:56浏览次数：19  
标签：二分 right int pos mid check left

时间复杂度

连续自然数和

对一个给定的正整数 $M$，求出所有的连续的正整数段（每一段至少有两个数），这些连续的自然数段中的全部数之和为 $M$。

例子：$1998+1999+2000+2001+2002 = 10000$，所以从 $1998$ 到 $2002$ 的一个自然数段为 $M=10000$ 的一个解。

题目看到是连续数字相加，就可以用前缀和，可以化解为找两点L和R， 使得sum[R] - sum[L - 1] 的和为 m。这里就可以从L=1到n开始便利，lower_bound函数找到满足sum[L - 1] + m = sum[R]条件的下标,输出即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n, i, ix;
    cin >> n;
    vector<int> sum(n + 5);
    sum[0] = 0;
    for (i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + i;
    for (i = 0; i < n; i++)
    {
        ix = lower_bound(sum.begin() + i + 1, sum.end(), n + sum[i]) - sum.begin();
        if (sum[ix] == sum[i] + n && ix - (i + 1) + 1 > 1)
        {
            cout << i + 1 << " " << ix << endl;
        }
    }
}

数列分段 Section II

对于给定的一个长度为 $N$ 的正整数数列 $A_{1\sim N}$，现要将其分成 $M$（$M\leq N$）段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：

例如一数列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段。

将其如下分段：

$$[4\ 2][4\ 5][1]$$

第一段和为 $6$，第 $2$ 段和为 $9$，第 $3$ 段和为 $1$，和最大值为 $9$。

将其如下分段：

$$[4][2\ 4][5\ 1]$$

第一段和为 $4$，第 $2$ 段和为 $6$，第 $3$ 段和为 $6$，和最大值为 $6$。

并且无论如何分段，最大值不会小于 $6$。

所以可以得到要将数列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段，每段和的最大值最小为 $6$。



解：
对于求最大值的最小值的问题是典型的二分问题，无法找出直接解决问题的思路，使用二分，以O(log2n)的速度找出答案 (在[0, 1e5]的范围内，精确到1e-8只需要44次)

这道题二分最大和的最小值，最大和设为x, 范围在[max of array, sum of array]中，规定了划分为m个区间，对于 x 较小的，会使得划分的区间数比m大， x较大的划分的区间数会比m小， 通过合理二分我们能找到合法且最小的区间。

(为了寻找x的最小合法值，二分向答案靠近，设check()函数的条件为 num <= k 即当前区间数较小或相等时，在二分时x选的过大或是在满足条件的一个值[不一定为最大值的最小值]将右边界缩小，而选取x过小时，left = mid + 1 说明最后二分结果一定在left = mid + 1 = right 这个情况是在x选取过小到x刚好合法的时候，即最后答案要求的最小满足的答案。由此我们也可以推出当改变条件边界，也可求出题目要求的最大值，改变check(num >= m), left = mid, right = mid - 1)

二分想好了，其实划分区间也很简单，就是通过贪心，尽量将能放在一起的放在一起。
在遍历整个数组的过程中，累加当前区间的总和sum，若此时加入a[i]后，sum + a[i] > x,这说明区间已满，需要再新开一个区间，每次新开记录数量，即得当前x的区间数num。

二分条件：

  1. 当分段数num > m时，指定最大值太小， left = mid + 1
  2. 当分段数num = m时，指定分段数合法，继续向左边看有无更小的，保留当前边界
  3. 当分段数num < m时, 指定最大值太大， right = mid；
int check(int x)
{
    int sum = 0, num = 1;
    for (int i = 1; i <= n; i++)
    {
        if (sum + a[i] <= x)
            sum += a[i];
        else
        {
            sum = a[i];
            num++;
        }
    }
    return num <= m;
}

while (left < right)
    {
        mid = (left + right) >> 1;
        if (check(mid))
        {
            right = mid;
        }
        else
            left = mid + 1;
    }

完整代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], n, k;
bool check(int x)
{
    int duan = 0, now = 0;
    for (int i = 1; i <= n; i++)
    {
        if (now + a[i] <= x)
        {
            now += a[i];
        }
        else
        {
            now = a[i];
            duan++;
            if (duan > k)
                return 0;
        }
    }
    if (now)
        duan++;
    return duan <= k;
}
int main()
{
    int left, right, mid, maxx = 0, sum = 0;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        maxx = max(a[i], maxx);
        sum += a[i];
    }
    left = maxx;
    right = sum;
    while (left < right)
    {
        mid = (left + right) >> 1;
        if (check(mid))
        {
            right = mid;
        }
        else
            left = mid + 1;
    }
    cout << right << endl;
}

你可能会问 如果x选的值是使得num合法的判断，但是没有一个区间达到了最大值，但其实此时达到合法值了，但是为了找到更小的会向左寻找更小的x，直到此时x满足某个区间为最大值。

抽象出最大值最小化，最小值最大化的模型：

找出二分范围， 用check条件判断，提前找出题目限制条件。




通往奥格瑞玛的道路

题目背景

在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量。

有一天他醒来后发现自己居然到了联盟的主城暴风城。

在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛。

题目描述

在艾泽拉斯，有 $n$ 个城市。编号为 $1,2,3,\ldots,n$。

城市之间有 $m$ 条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。

每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。

假设 $1$ 为暴风城，$n$ 为奥格瑞玛，而他的血量最多为 $b$，出发时他的血量是满的。如果他的血量降低至负数，则他就无法到达奥格瑞玛。

歪嘴哦不希望花很多钱，他想知道，在可以到达奥格瑞玛的情况下，他所经过的所有城市中最多的一次收取的费用的最小值是多少。

输入格式

第一行 $3$ 个正整数，$n,m,b$。分别表示有 $n$ 个城市，$m$ 条公路，歪嘴哦的血量为 $b$。

接下来有 $n$ 行，每行 $1$ 个正整数，$f_i$。表示经过城市 $i$，需要交费 $f_i$ 元。

再接下来有 $m$ 行，每行 $3$ 个正整数，$a_i,b_i,c_i$（$1\leq a_i,b_i\leq n$）。表示城市 $a_i$ 和城市 $b_i$ 之间有一条公路，如果从城市 $a_i$ 到城市 $b_i$，或者从城市 $b_i$ 到城市 $a_i$，会损失 $c_i$ 的血量。

输出格式

仅一个整数，表示歪嘴哦交费最多的一次的最小值。

如果他无法到达奥格瑞玛，输出 AFK。

//大TLE TLE TLE
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e4 + 5;
pair<int, int> f[N];
int a[N][N], dis[N], vis[N];
int n, m, b;
bool check(int x)
{
    // cout << "!11" << endl;
    int i, j, xx;
    vector<int> aa;
    for (i = 1; i <= x; i++)
        aa.push_back(f[i].first);
    for (i = 1; i <= n; i++)
        dis[i] = 1e18;
    memset(vis, 0, sizeof(vis));
    dis[1] = 0;
    int ff, minn;
    while (1)
    {
        minn = 0x3f;
        ff = -1;
        for (auto pos = aa.begin(); pos != aa.end(); ++pos)
        {
            xx = *pos;
            if (!vis[xx] && minn > dis[xx])
            {
                ff = xx;
                minn = dis[xx];
            }
        }
        if (ff == -1)
            break;
        vis[ff] = 1;
        for (auto pos = aa.begin(); pos != aa.end(); ++pos)
        {
            i = *pos;
            if (a[i][ff] != 0)
                dis[i] = min(dis[i], dis[ff] + a[i][ff]);
        }
    }
    cout << dis[n] << endl;
    if (dis[n] <= b)
        return true;
    return false;
}
bool cmp(pair<int, int> a, pair<int, int> b)
{
    if (a.second == b.second)
        return a.first < b.first;
    return a.second < b.second;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int i, x, y, ss, j;
    cin >> n >> m >> b;
    for (i = 1; i <= n; i++)
    {
        cin >> f[i].second;
        f[i].first = i;
    }
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= i; j++)
        {
            a[i][j] = 1e9;
            a[j][i] = 1e9;
        }
    }
    int f1 = max(f[1].second, f[n].second);
    for (i = 0; i < m; i++)
    {
        cin >> x >> y >> ss;
        a[x][y] = ss;
        a[y][x] = ss;
    }
    sort(f + 1, f + 1 + n, cmp);
    int left = 1, right = n, mid;
    while (left < right)
    {
        mid = (left + right) >> 1;
        if (check(mid))
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    if (!check(right))
        cout << "AFK" << endl;
    else
    {
        cout << f[right].second << endl;
    }
}


解：
将最大值收入的最小值进行二分，check()函数内使用dijkstra算最短路径，注意最短路径时，要考虑路径的存储，用链式前向星来存，矩阵数组空间冗余过多会报错，在while循环内找当前最短dis时，也需要用到更优化的结构，把从1到每一个点的最短路径dis[n]用小根堆 + pair的形式存，即优先队列 priority_queue<pair<int, int="">, vector<pair<int, int="">>, greater<pair<int, int="">>> que 使得在存储的时候拿取的时间在O(logn),这题也卡时间。 这样存储在 366ms 内存在3.36MB 原先粗糙代码在 477ms 128MB在大数据的情况下内存完全超限制

compare: 链式前向星的存储方式完全适配于dijkstra的算法，在寻找到最小的dis[n]时，重新更新所有未进队的节点dis值，直接便利head即可，存取都十分方便，还有就是时间复杂度上面，没有必要每一次check()都进行一次预处理把可以走的节点拉出来，直接在dijkstra更新的时候直接加上判断条件，收费值大于x的直接不更新，也不会进队，直接屏蔽。 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e4 + 5;
const int M = 1e5 + 5;
int n, m, b, f[N], vis[N], dis[N];
int cnt = 0, head[N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
struct edge
{
    int to, next, s;

} ed[M];
void add(int xx, int yy, int ss)
{
    ed[++cnt].to = yy;
    ed[cnt].next = head[xx];
    head[xx] = cnt;
    ed[cnt].s = ss;
}
bool check(int x)
{
    int ddis, index, i, yy, cost;
    memset(vis, 0, sizeof(vis));
    for (i = 1; i <= n; i++)
        dis[i] = 1e9;
    if (f[1] > x || f[n] > x)
        return 0;
    dis[1] = 0;
    que.push({0, 1});
    while (!que.empty())
    {
        index = que.top().second;
        ddis = que.top().first;
        que.pop();
        if (vis[index])
            continue;
        vis[index] = 1;
        for (i = head[index]; i != -1; i = ed[i].next)
        {
            yy = ed[i].to;
            cost = ed[i].s;
            if (f[yy] <= x && !vis[yy] && dis[yy] > ddis + cost)
            {
                dis[yy] = ddis + cost;
                que.push({dis[yy], yy});
            }
        }
    }
    if (dis[n] <= b)
        return 1;
    return 0;
}
signed main()
{
    int i, xx, yy, ss, maxx = 0, minn = 1e9 + 10;
    cin >> n >> m >> b;
    for (i = 0; i < n; i++)
    {
        cin >> f[i + 1];
        maxx = max(maxx, f[i + 1]);
        minn = min(minn, f[i + 1]);
    }
    memset(head, -1, sizeof(head));
    for (i = 0; i < m; i++)
    {
        cin >> xx >> yy >> ss;
        add(xx, yy, ss);
        add(yy, xx, ss);
    }
    int left = minn, right = maxx, mid;
    while (left < right)
    {
        mid = (left + right) >> 1;
        if (check(mid))
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    if (!check(maxx))
    {
        cout << "AFK" << endl;
    }
    else
    {
        cout << left << endl;
    }
}

后置知识

链式前向星+小根堆dijstra

小根堆定义
//队列内类型，容器，排列方式（仿函数）
priority_queue<pair<int, int>, vector<int, int>, greater<pair<int, int>>>;
链式前向星定义：
struct edge
{
    int to, next, len;
} e[M];
添加边：
void add(int x, int y, int z)
{
    e[++t].len = z;
    e[t].to = y;
    e[t].next = head[x];
    head[x] = t;
}

便利方式：
    s2 = head[ff];
    while (s2 != -1)
    {
    }

进击的奶牛

题目描述

Farmer John 建造了一个有 $N$（$2 \leq N \leq 10 ^ 5$) 个隔间的牛棚，这些隔间分布在一条直线上，坐标是 $x _ 1, x _ 2, \cdots, x _ N$（$0 \leq x _ i \leq 10 ^ 9$）。

他的 $C$（$2 \leq C \leq N$）头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗，Farmer John 想把这些牛安置在指定的隔间，所有牛中相邻两头的最近距离越大越好。那么，这个最大的最小最近距离是多少呢？

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n, c, pos[N];
bool check(int x)
{
    int now = 0, num = 1;
    for (int i = 1; i < n; i++)
    {
        if (now < x)
        {
            now += pos[i + 1] - pos[i];
        }
        else
        {
            num++;
            now = pos[i + 1] - pos[i];
        }
    }
    if (now >= x)
        num++;
    return num >= c;
}
signed main()
{
    int i;
    cin >> n >> c;
    for (i = 1; i <= n; i++)
        cin >> pos[i];
    sort(pos + 1, pos + n + 1);
    int minn = 1e18, maxx = pos[n] - pos[1];
    for (i = 1; i < n; i++)
    {
        minn = min(minn, pos[i + 1] - pos[i]);
    }
    int left = minn, right = maxx, mid;
    while (left < right)
    {
        mid = (left + right + 1) / 2;
        if (check(mid))
            left = mid;
        else
            right = mid - 1;
    }
    cout << left << endl;
}

解：二分求相邻奶牛最小距离的最大值，板刷题目。二分距离范围在[最小的间距，第一个牛棚到最后一个的距离]。

标签：二分,right,int,pos,mid,check,left
From： https://www.cnblogs.com/yingtaoqqq/p/18206973

相关文章

  • 二分答案 洛谷P3853路标设置
    这个题思路和洛谷P2440有点像，建议先看P2440这个题，较简单。[TJOI2007]路标设置题目背景B市和T市之间有一条长长的高速公路，这条公路的某些地方设有路标，但是大家都感觉路标设得太少了，相邻两个路标之间往往隔着相当长的一段距离。为了便于研究这个问题，我们把公路上相邻路标的最......
  • 二分答案 洛谷2440木材加工
    二分答案题目详见洛谷P2440木材加工分享一下自己新学习的二分答案的方法，开始可能有点奇怪为啥这样能做，但其实思路很简单。起始思路题目要求我们求最大的分解长度，所以我（们）最开始想的肯定是从大到小（求最大值）枚举答案，看看是否满足，满足不了就加1。但这样暴力肯定是会超时的，那我们......
  • 代码随想录算法训练营第一天|704,34,35(二分查找),27(双指针)
    二分查找1.使用条件：数组，升序，值不唯一。2.时间复杂度O(logn)可分为左闭右闭，左闭右开两种区间类型来求解。左闭右闭:left=0,right=nums.Length-1,while(left<=right),right=middle-1.左闭右开:left=0,right=nums.Length,while(left<right),right=middle.......
  • 算法随想录打卡第一天|704. 二分查找、27. 移除元素
    704.二分查找-力扣（LeetCode）自己的解法是这样的，超出了时间限制，现在觉得应该是在mid的计算中出了问题。然后在mid的转换中没有right减去1或者left加上1。这两点的问题。自己很习惯的方式是左闭合加上右闭合。可以省去很多对于临界值忘记考虑的麻烦。超时代码贴出：publicin......
  • 二分图
    二分图定义：一张图的\(N\)个节点可以分为\(A,B\)两个非空集合，满足同一个集合中的任意两个点没有连边。集合\(A,B\)分别叫做二分图的左部和右部，如图所示：二分图的判定交替染色，只有相邻的点颜色不一样时才可能是二分图，定理：二分图一定不存在奇环（易证）。判定：搜索\(dfs\)或......
  • 二分图的最大匹配（匈牙利算法）代码
    二分图的最大匹配代码#include<bits/stdc++.h>usingnamespacestd;constintN=505,M=100005;inth[N],e[M],ne[M],idx;intmatch[N];boolst[N];intn1,n2,m;voidadd(inta,intb){e[idx]=b;//e[idx]存放的是第idx条边的终点ne[idx]=h......
  • 二分查找
    输入 n 个不超过 10九次方 的单调不减的（就是后面的数字不小于前面的数字）非负整数 ......
  • luoguP1163-二分
    银行贷款题目链接：https://www.luogu.com.cn/problem/P1163本题思路：orz公式数学公式给出n,m,k，求贷款者向银行支付的利率p，使得:$\sum_{i=1}^{k}m*[\frac{1}{1+p}]^{i}$，通过化简(根据等比数列的求和公式)我们有：$m\frac{1-\left(\frac{1}{1+p}\right)^k}{1-\frac{......
  • P6577 【模板】二分图最大权完美匹配 （KM）
    $\quad$初看就发现不对劲了，模板紫题，一看就不简单，就交了个裸\(KM\)，哎，果然\(T\)了。$\quad$然后就是大力卡常（当然\(O(n^4)\)）的复杂度不是卡常能解决的。遂看题解，发现一个据说\(O(n^3)\)的复杂度的\(KM\)，也是非常抽象。具体解释详见https://www.luogu.com.cn/article/ip2m1gu......
  • 二分图
    关于二分图判断是否为二分图左部和右部的点之间不存在连边，即不存在奇环；codes点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e5+10;intn,m,tot;intto[maxn*2],nxt[maxn*2],w[maxn*2],h[maxn];intcol[maxn],x[maxn],y[maxn],z[maxn];......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99