Rikkar

二分

1024程序员节(1) C++(3) codeforces(5) dp(3) game(1) git(1) java(4) javaweb(2) math(14) maven(2) mysql(1) VS(2) 区域赛(1) 图(2) 思维(30) 数据结构(2) 新手入门(1) 暴力(3) 未归档(6) 板子(7) 构造(2) 模拟(3) 比赛(1) 笔记(1) 算法(27) 蓝桥杯(20) 规律(1) 贪心(1) 资料(1) 面试题集(1) 项目(1) 题解(44)

/ 注册

全部文章 / 二分（共5篇）

D. Max Median （二分、思维）

题目从结果分析，答案必定是数组中的一个值，那么我们将值排个序开始二分。check的话，对于我们将要检查的值mid，将原数组中所有小于mid的值设为-1，大于等于mid的值设为1，对于一段区间看其中位数是否>=mid，只要看变化后该区间的总和，如果>0则其中位数>=mid。用一个...

2021-12-18

0 661

C2. Guessing the Greatest (hard version) (二分、思维)

题目对于easy情况的做法是，对每个范围都询问两次第二大值，借用第二大值确定最大值所在范围，然后缩小范围。 hard情况的做法是，先询问第二大值所在位置p，然后根据最大值所在其左还是右分情况进行二分，其比easy询问次数少了一半是因为每次问询都使用mid—p（假设最大值在p左边），如果第二大值...

2021-12-18

0 598

Cable master POJ - 1064 (二分精度)

题目思路：二分每条绳子的长度，循环100次即可。判断条件：每一段向下取整求最大可以裁剪的数量，如果所有数量大于等于k则满足l=mid,小于则不满足r=mid。使用流输出还需注意cout规定小数精度后是四舍五入的，但printf是只截取前多少位。 #include<iostream>...

2021-12-18

0 524

Aggressive cows POJ - 2456 (二分---最小化最大值)

题目二分距离判断条件就是从一开始每发现一个>=d时放一头牛，如果能全部放完l=mid,否r=mid-1,mid=(l+r+1)/2。 #include<iostream> #include<cmath> #include<iomanip> #...

2021-12-18

0 376

D - Minimax Problem （二分、状压）

题目思路：首先暴力想一想这道题，把每两组数都模拟一遍取最大值，O(N^2)。然后看有没有什么地方可以改进，会发现这题可以适用于二分，看可以用二分的条件—单调（而本题从某种方面看也是“单调”的，所要求的最大值ans,值越小就越不可能成立，越大则越可能成立）,故设立一个范围l=0,r=1e9，二分出...

2021-12-18

0 557