二分答案(定义,做法,最短子序列问题,力扣分享巧克力,洛谷P2678 [NOIP2015 提高组] 跳石头,atcoder D - Widespread,牛客小黑月赛37 I-加减)

本文主要是介绍二分答案(定义,做法,最短子序列问题,力扣分享巧克力,洛谷P2678 [NOIP2015 提高组] 跳石头,atcoder D - Widespread,牛客小黑月赛37 I-加减),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

二分答案

定义

做法

最短子序列问题

解题思路:

力扣 分享巧克力

解题思路:

结论:

洛谷P2678 [NOIP2015 提高组] 跳石头

解题思路:

atcoder D - Widespread

解题思路:

牛客小黑月赛37 I-加减

解题思路:


二分答案

定义

它是二分思想的一个进阶技巧。通过观察发现问题的答案存在单调性,通过二分答案后检查答案是否能够达到。

直观来讲,二分答案就是一种(因为答案有单调性,所以)利用二分思想优化枚举答案过程的算法

做法

1.发现答案的单调性

2.二分答案

3.检查答案是否可行(每道题的重点在这)

最短子序列问题

给定一个正整数序列,让你取一个子段,使得其区间的和大于等于$x$,问你这个子段最短可能长度是多少。

解题思路:

首先预处理前缀和(方便后面计算区间和),然后用二分的思想来找答案的长度,这道题的答案是最短子序列的长度,检查函数内,通过一个滑动窗口来选中mid个元素,每次保留最大值,原因是最大值最容易满足>=x,最后传回判断,再缩减左右端点,因为答案是越靠后越容易实现,所以此题为后缀模型,所以输出L

#include <iostream>
using namespace std;
int a[1005], s[1005] = {0}, n, x;int ok(int mid)
{int mx = 0;//i为答案的长度for(int i = mid; i <= n ; i++){//i-mid 与 i 之间构成了长度为 mid 的滑动窗口//每次求最大值,原因是最大值是最有可能满足>=x的mx = max(mx, s[i] - s[i - mid]);}//最后传回判断return mx >= x;
}int main()
{cin >> n >> x;//输入序列,预处理前缀和for(int i = 1; i <= n; i++){cin >> a[i];s[i] = s[i-1] + a[i];}int l = 1, r = n, mid;while(l <= r){mid = (l + r) >> 1;//cout << mid << " " << ok(mid) << endl;//用检查函数来判断更改哪个端点,如果判断函数传回满足,就缩减右端点//如果不满足就缩减左端点, 因为题目是给一个升序的序列,越往后越容易实现题目要求if(ok(mid))r = mid - 1;else l = mid + 1;}//此题为后缀模型,越往后越容易实现题目要求cout << l;return 0;
}

力扣 分享巧克力

解题思路:

#include <iostream>using namespace std;
int n, k, a[10005], maxn = 0;int ok(int mid)
{int o = 0, sum1 = 0;//从第一个位置开始累加for(int i = 1; i <= n; i++){sum1 += a[i];//当sum1满足了我们mid(枚举的甜度),那么就记一次数if(sum1 >= mid){sum1 = 0;o++;}}//最终要判断我们是否满足了题目要求分成k+1块,如果分的比k+1要多,对于我们答案来说是不影响的return o >= k + 1;
}int main()
{cin >> n >> k;for(int i = 1; i<= n; i++){cin >> a[i];//存下数组里面最甜的那一块if(maxn < a[i])maxn = a[i];}int l = 1, r = maxn;while(l <= r){int mid = (l + r) >> 1;//这是一个前缀模型,通过ok函数进行端点的变动if(ok(mid))l = mid + 1;else r = mid - 1;}cout << r;return 0;
}
/*
9 5
1 2 3 4 5 6 7 8 9
*/

结论:

求最小值的最大值是前缀模型

求最大值的最小值是后缀模型

洛谷P2678 [NOIP2015 提高组] 跳石头

题目链接:[NOIP2015 提高组] 跳石头 - 洛谷

解题思路:

答案是求最小值的最大值,而且答案一定是 1 <= ans <= l,所以我们很自然可以想到二分答案前缀和,因为越小越容易实现,然后我们通过OK函数来判断,mid当ans是否成立,在ok函数中,通过判断后一块与前一块的距离是否满足>=mid,不满足就撤一块,再用后一块与当前的前一块进行比较,所以加了一个变量q储存用来减去的石头,最后判断撤走的石头满不满足题目要求,最终输出R,因为是前缀模型

#include<bits/stdc++.h>
using namespace std;#define ll long long
const int maxn = 5e4 + 5;
int l, n, m;
int a[maxn] = {0};int ok(int mid)
{//cnt是撤走的石头数量,q是储存用于减去的石头的下标int cnt = 0, q = 0;//枚举每一块石头for(int i = 1; i <= n + 1; i++){//判断之间的距离满不满足>=mid,不满足就撤走一块石头,再进行判断if(a[i] - a[q] < mid){cnt++;}else{//满足条件就储存当前的下标,用于下一次比较q = i;}}//返回撤走的石头数是否满足题目要求return cnt <= m;
}int main()
{cin >> l >> n >> m;//输入石头距离for(int i = 1; i <= n; i++)cin >> a[i];//终点特殊处理a[n+1] = l;int le = 1, r = l;//二分答案while(le <= r){int mid = (le + r) >> 1;if(ok(mid))le = mid +1;else r = mid - 1;}//前缀模型输出Rcout << r;return 0;
}

atcoder D - Widespread

题目链接:D - Widespread

题目大意:给你n个正整数,你有一个操作是让一个数减A,然后让其他数减B.保证A > B问你最少多少次操作能够让所有数降到<=0

1≤N≤10^5

1 ≤ B < A ≤ 10^9

1 ≤ h_i ≤ 10^9

解题思路:

题目求操作,肯定是操作越多越容易实现,所以这是一个二分答案后缀模型,左右端点分别为2,1e9(假设所有数为1,假设B为1),用一个ok函数判断mid答案是否合法,在ok函数中判断当前的w[i]是否小于等于b*mid(答案数乘B),如果小于就不用消耗我们的次数(A-B的差值),如果大于的话我们就需要消耗mid次数(这里我用K来存),消耗完之后还要进行一次判断,因为第一次消耗可能是3/2=1,剩下还有一个1没消耗完,所以我们手动还要消耗一次,最后判断一下次数是否变为负数,如果变负数直接返回false,出了for循环就代表k>=0,返回true

这道题给我的教训就是,大数据一定要用long long,这道题为此浪费了半个多小时!!!

#include<bits/stdc++.h>
using namespace std;#define ll long long
const ll maxn = 1e5 + 5;
ll n, a, b;
ll w[maxn];int ok(ll mid)
{ll k = mid;//遍历所有元素for(ll i = 1; i <= n; i++){//如果小于mid答案*B就不处理if(w[i] <= b*mid)continue;//否则就消耗次数k -= (w[i]-b*mid) / (a-b);//如果碰到不整除的情况就需要手动加一次if((w[i]-b*mid) - (w[i]-b*mid)/(a-b)*(a-b) > 0)k -= 1;//次数如果变为负数就返回falseif(k < 0)return 0;}//出了循环就代表k>=0return 1;
}int main()
{cin >> n >> a >> b;for(int i = 1; i <= n; i++)cin >> w[i];//假设所有数为1,假设B为1,左右端点ll l = 1, r = 1e9;while(l <= r){int mid = (l + r) >> 1;//检查答案是否合法if(ok(mid))r = mid - 1;else l = mid +1;}//这是一个二分答案后缀模型cout << l;return 0;
}

牛客小黑月赛37 I-加减

题目链接:牛客小黑月赛37 I-加减

解题思路:

题目要求出现最多元素的次数,我们自然想到二分答案前缀模型,因为满足<=k,答案越小越容易实现,开始我们做一个前缀和处理,方便后面通过中位数来加消耗的次数(就不用写绝对值来求次数了),进入OK函数,因为我们L和R枚举的是出现的次数,所以我们用一个滑动窗口来从开头往后遍历,判断次数是否小于K(我们先mid*(mid到左边下标-1)的个数,然后减去这一段的和,因为是排好序的,所以求出来就是需要加1的操作次数,第二部分,我们用(右下标的前缀和-mid位置的前缀和),得到的就是右下标到mid+1位置的这一段,因为是排好序的,所以这一段都比mid大,所以要对这些原素做-1操作,所以这些也加入操作数),跳出循环后就一定>k所以返回false

#include<bits/stdc++.h>
using namespace std;#define ll long long
const ll maxn = 1e5 + 5;
ll a[maxn];
ll sum1[maxn];
ll n, k;ll ok(ll mid)
{//做一个滑动窗口for(ll i = 1; i+mid-1 <= n; i++){//求出中位数ll midd = (i + i + mid - 1) >> 1;//见代码加粗部分if(a[midd]*(midd-i+1)-(sum1[midd]-sum1[i-1])+(sum1[i+mid-1]-sum1[midd])-a[midd]*(i+mid-1-midd) <= k)return true;}return false;
}int main()
{cin >> n >> k;for(int i = 1; i <= n; i++)cin >> a[i];//排序,这样在后续可以通过中位数来求sort(a+1, a+n+1);for(int i = 1; i <= n; i++)sum1[i] = sum1[i-1] + a[i];//枚举出现元素次数的最小最大可能,用二分优化ll l = 1, r = n;while(l <= r){ll mid = (l + r) >> 1;if(ok(mid))l = mid + 1;else r = mid -1;}cout << r;return 0;
}

这篇关于二分答案(定义,做法,最短子序列问题,力扣分享巧克力,洛谷P2678 [NOIP2015 提高组] 跳石头,atcoder D - Widespread,牛客小黑月赛37 I-加减)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/227979

相关文章

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

Python解析器安装指南分享(Mac/Windows/Linux)

《Python解析器安装指南分享(Mac/Windows/Linux)》:本文主要介绍Python解析器安装指南(Mac/Windows/Linux),具有很好的参考价值,希望对大家有所帮助,如有... 目NMNkN录1js. 安装包下载1.1 python 下载官网2.核心安装方式3. MACOS 系统安

Java嵌套for循环优化方案分享

《Java嵌套for循环优化方案分享》介绍了Java中嵌套for循环的优化方法,包括减少循环次数、合并循环、使用更高效的数据结构、并行处理、预处理和缓存、算法优化、尽量减少对象创建以及本地变量优化,通... 目录Java 嵌套 for 循环优化方案1. 减少循环次数2. 合并循环3. 使用更高效的数据结构4

Python中常用的四种取整方式分享

《Python中常用的四种取整方式分享》在数据处理和数值计算中,取整操作是非常常见的需求,Python提供了多种取整方式,本文为大家整理了四种常用的方法,希望对大家有所帮助... 目录引言向零取整(Truncate)向下取整(Floor)向上取整(Ceil)四舍五入(Round)四种取整方式的对比综合示例应

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法:贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列,例如 nums = [10, 9, 2

linux进程D状态的解决思路分享

《linux进程D状态的解决思路分享》在Linux系统中,进程在内核模式下等待I/O完成时会进入不间断睡眠状态(D状态),这种状态下,进程无法通过普通方式被杀死,本文通过实验模拟了这种状态,并分析了如... 目录1. 问题描述2. 问题分析3. 实验模拟3.1 使用losetup创建一个卷作为pv的磁盘3.

MySQL8.2.0安装教程分享

《MySQL8.2.0安装教程分享》这篇文章详细介绍了如何在Windows系统上安装MySQL数据库软件,包括下载、安装、配置和设置环境变量的步骤... 目录mysql的安装图文1.python访问网址2javascript.点击3.进入Downloads向下滑动4.选择Community Server5.

CentOS系统Maven安装教程分享

《CentOS系统Maven安装教程分享》本文介绍了如何在CentOS系统中安装Maven,并提供了一个简单的实际应用案例,安装Maven需要先安装Java和设置环境变量,Maven可以自动管理项目的... 目录准备工作下载并安装Maven常见问题及解决方法实际应用案例总结Maven是一个流行的项目管理工具

10个Python自动化办公的脚本分享

《10个Python自动化办公的脚本分享》在日常办公中,我们常常会被繁琐、重复的任务占据大量时间,本文为大家分享了10个实用的Python自动化办公案例及源码,希望对大家有所帮助... 目录1. 批量处理 Excel 文件2. 自动发送邮件3. 批量重命名文件4. 数据清洗5. 生成 PPT6. 自动化测试