如何自己做网站腾讯,wordpress访问目录,活动策划怎么写,58同城百姓网目录 引言概念一、借教室二、分巧克力三、管道四、技能升级五、冶炼金属六、数的范围七、最佳牛围栏 引言
这几天一直在做二分的题#xff0c;都是上了难度的题目#xff0c;本来以为自己的二分水平已经非常熟悉了#xff0c;没想到还是糊涂了一两天才重新想清楚#xff0… 目录 引言概念一、借教室二、分巧克力三、管道四、技能升级五、冶炼金属六、数的范围七、最佳牛围栏 引言
这几天一直在做二分的题都是上了难度的题目本来以为自己的二分水平已经非常熟悉了没想到还是糊涂了一两天才重新想清楚想明白还是得继续不断地刷题把这些类型的题刷明白刷透了就可以了加油 概念
一般只有这两种情况具体模板可以参考之前的博客二分再特殊一点的就是本篇博客的第五、六题了但看我的解析都是一样的步骤。 一、借教室
标签二分
思路这道题如果用暴力来做的话就是遍历 m m m 个订单每个订单然后去判断是否正确去判断没天中的订单是否满足要求就这样也是 1 0 12 10^{12} 1012 明显超时了。可以用二分来做因为这个订单是具有单调性的假设第 k k k 个订单是第一个不满足要求的那么之后的订单也是不满足要求的判断依据就是定义一个天数数组 b [ i ] b[i] b[i] 每天的订单数是不能超过 w [ i ] w[i] w[i] 的所以可以用二分检查条件从而判断出第一个不满足的然后再 s j ∼ t j s_j\sim t_j sj∼tj天要用 d j d_j dj个教室可以用差分来做这样就可以了。 这相当于一个模型有多个订单每天进行多个操作问订单会不会满足条件.
题目描述
在大学期间经常需要租借教室。大到院系举办活动小到学习小组自习讨论都需要向学校申请借教室。教室的大小功能不同借教室人的身份不同借教室的手续也不一样。 面对海量租借教室的信息我们自然希望编程解决这个问题。我们需要处理接下来 n 天的借教室信息其中第 i 天学校有 ri 个教室可供租借。共有 m 份订单每份订单用三个正整数描述分别为 dj,sj,tj表示某租借者需要从第 sj 天到第 tj 天租借教室包括第 sj天和第 tj 天每天需要租借 dj 个教室。 我们假定租借者对教室的大小、地点没有要求。即对于每份订单我们只需要每天提供 dj 个教室而它们具体是哪些教室每天是否是相同的教室则不用考虑。 借教室的原则是先到先得也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足则需要停止教室的分配通知当前申请人修改订单。这里的无法满足指从第 sj 天到第 tj 天中有至少一天剩余的教室数量不足 dj 个。 现在我们需要知道是否会有订单无法完全满足。如果有需要通知哪一个申请人修改订单。输入格式
第一行包含两个正整数 n,m表示天数和订单的数量。
第二行包含 n 个正整数其中第 i 个数为 ri表示第 i 天可用于租借的教室数量。
接下来有 m 行每行包含三个正整数 dj,sj,tj表示租借的数量租借开始、结束分别在第几天。
每行相邻的两个数之间均用一个空格隔开。
天数与订单均用从 1 开始的整数编号。输出格式
如果所有订单均可满足则输出只有一行包含一个整数 0。
否则订单无法完全满足输出两行第一行输出一个负整数 −1第二行输出需要修改订单的申请人编号。数据范围
1≤n,m≤106,0≤ri,dj≤109,1≤sj≤tj≤n
输入样例
4 3
2 5 4 3
2 1 3
3 2 4
4 2 4
输出样例
-1
2示例代码
#include bits/stdc.husing namespace std;typedef long long LL;const int N 1e610;int n, m;
int w[N];
int d[N], s[N], t[N];
LL b[N];bool check(int mid)
{memset(b, 0, sizeof b);for(int i 1; i mid; i){b[s[i]] d[i];b[t[i]1] - d[i];}for(int i 1; i n; i){b[i] b[i-1];if(b[i] w[i]) return true;}return false;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n m;for(int i 1; i n; i) cin w[i];for(int i 1; i m; i) cin d[i] s[i] t[i];int l 1, r m;while(l r){int mid l r 1;if(check(mid)) r mid;else l mid 1;}if(check(r)){cout -1 endl;cout r endl;}else{cout 0 endl;}return 0;
}二、分巧克力
标签二分
思路这道题首先满足单调性分的巧克力的大小在一定值后就不能切除 K K K 块巧克力了所以可以用二分来求答案。
题目描述
儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有 N 块巧克力其中第 i 块是 Hi×Wi 的方格组成的长方形。为了公平起见小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足形状是正方形边长是整数大小相同例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3 的巧克力。当然小朋友们都希望得到的巧克力尽可能大你能帮小明计算出最大的边长是多少么输入格式
第一行包含两个整数 N 和 K。
以下 N 行每行包含两个整数 Hi 和 Wi。
输入保证每位小朋友至少能获得一块 1×1 的巧克力。输出格式
输出切出的正方形巧克力最大可能的边长。数据范围
1≤N,K≤105,1≤Hi,Wi≤105
输入样例
2 10
6 5
5 6
输出样例
2示例代码
#include bits/stdc.husing namespace std;typedef long long LL;const int N 1e510;int n, k;
int h[N], w[N];bool check(int mid)
{LL s 0;for(int i 1; i n; i){s ((LL)h[i] / mid) * (w[i] / mid);if(s k) return true;}return false;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n k;for(int i 1; i n; i) cin h[i] w[i];int l 1, r 1e5;while(l r){int mid l r 1 1;if(check(mid)) l mid;else r mid - 1;}cout r endl;return 0;
}三、管道
标签二分
思路这道题一看是求最早的时间根据题意可以知道时间到了一定的值那么后面的时间都可以满足条件那么可以利用二分来枚举时间然后根据判断条件来找到满足条件的第一个点。然后判断条件可以通过时间来算出来每个阀门在当前时间能够经过的区间然后把这些区间合并如果最后的区间包含了所有的区间那么就是满足条件的。而且这个区间可以是不重叠也可以合并的因为 [ 1 , 2 ] [1,2] [1,2] 和 [ 3 , 4 ] [3,4] [3,4] 都能覆盖到那么说明 [ 1 , 4 ] [1,4] [1,4] 都能检测道水流。
题目描述
有一根长度为 len 的横向的管道该管道按照单位长度分为 len 段每一段的中央有一个可开关的阀门和一个检测水流的传感器。一开始管道是空的位于 Li 的阀门会在 Si 时刻打开并不断让水流入管道。对于位于 Li 的阀门它流入的水在 TiTi≥Si时刻会使得从第 Li−(Ti−Si) 段到第 Li(Ti−Si) 段的传感器检测到水流。求管道中每一段中间的传感器都检测到有水流的最早时间。输入格式
输入的第一行包含两个整数 n,len用一个空格分隔分别表示会打开的阀门数和管道长度。接下来 n 行每行包含两个整数 Li,Si用一个空格分隔表示位于第 Li 段管道中央的阀门会在 Si 时刻打开。输出格式
输出一行包含一个整数表示答案。数据范围
对于 30% 的评测用例n≤200Si,len≤3000
对于 70% 的评测用例n≤5000Si,len≤105
对于所有评测用例1≤n≤1051≤Si,len≤1091≤Li≤lenLi−1Li。输入样例
3 10
1 1
6 5
10 2
输出样例
5示例代码
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;const int N 1e510;int n, len;
int L[N], S[N];
PII segs[N];bool check(int mid)
{int cnt 0;for(int i 1; i n; i){if(mid S[i]){int t mid - S[i];int l max(1, L[i] - t), r min((LL)len, (LL)L[i] t);segs[cnt] {l,r};}}sort(segs, segscnt);int l -2e9, r -2e9;for(int i 0; i cnt; i){if(segs[i].first r 1) l segs[i].first, r segs[i].second;else r max(r, segs[i].second);}return l 1 r len;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n len;for(int i 1; i n; i) cin L[i] S[i];int l 0, r 2e9; // 等到1e9开阀门再经过1e9从左边流到右边while(l r){int mid (LL)l r 1;if(check(mid)) r mid;else l mid 1;}cout r endl;return 0;
}四、技能升级
标签二分
思路1首先这道题先用了堆来做过了7/12个数据代码随后附上。
思路2做题首先要先到怎么做出来然后再想时间复杂度的问题首先这道题肯定是把所有的数加起来然后从大到小排序选前 M M M 个数就是最大的那么实际上也是从这里面选前 M M M 个最大的数。那么我们假设第 M M M 个数为 x x x 那么一定满足大于等于 x x x 的个数一定是大于等于 M M M 的并且大于等于 x 1 x1 x1的个数一定是小于 M M M 个的因为x越大值就越少越小值就越多然后可以求出来 x x x 然后最后的结果和个数可以通过数学公式来推出来最后还要统计个数如果超 M M M 个了这是因为可能有跟 x x x 一样的数所以减去多余的即可。 模型多路归并算法 题目描述
小蓝最近正在玩一款 RPG 游戏。他的角色一共有 N 个可以加攻击力的技能。其中第 i 个技能首次升级可以提升 Ai 点攻击力以后每次升级增加的点数都会减少 Bi。⌈AiBi⌉上取整次之后再升级该技能将不会改变攻击力。现在小蓝可以总计升级 M 次技能他可以任意选择升级的技能和次数。请你计算小蓝最多可以提高多少点攻击力输入格式
输入第一行包含两个整数 N 和 M。
以下 N 行每行包含两个整数 Ai 和 Bi。输出格式
输出一行包含一个整数表示答案。数据范围
对于 40% 的评测用例1≤N,M≤1000
对于 60% 的评测用例1≤N≤1041≤M≤107
对于所有评测用例1≤N≤1051≤M≤2×1091≤Ai,Bi≤106。输入样例
3 6
10 5
9 2
8 1
输出样例
47示例代码一 堆 7/12
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;
#define x first
#define y secondconst int N 1e510;int n, m;
int a[N], b[N];
priority_queuePII heap;int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n m;for(int i 1; i n; i) {cin a[i] b[i];heap.push({a[i], b[i]});}LL res 0;while(m-- heap.size()){auto t heap.top(); heap.pop();res t.x;if(t.x - t.y 0) continue; //为0的就不加进去了加了最大值也不变还会增加时间复杂度heap.push({t.x-t.y, t.y});}cout res endl;return 0;
}示例代码二 二分 12/12
#include bits/stdc.husing namespace std;typedef long long LL;const int N 1e510;int n, m;
int a[N], b[N];bool check(int mid)
{LL s 0;for(int i 1; i n; i){if(a[i] mid){s (a[i] - mid) / b[i] 1;if(s m) return true;}}return false;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n m;for(int i 1; i n; i) cin a[i] b[i];int l 0, r 1e6; // l可能取0即全部包含进去while(l r){int mid l r 1 1;if(check(mid)) l mid;else r mid - 1;}LL res 0, cnt 0;for(int i 1; i n; i){if(a[i] r){int c (a[i] - r) / b[i] 1;int end a[i] - (c - 1) * b[i];cnt c;res (LL)(a[i] end) * c / 2;}}cout res - (cnt - m) * r endl;return 0;
}五、冶炼金属
标签二分
思路这道题其实就是如下图所示的一种二分在满足条件的情况下找到 m i d mid mid 的最小值和最大值然后就是一些细节问题我标在注释里了。
题目描述
小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 VV 是一个正整数这意味着消耗 V 个普通金属 O 恰好可以冶炼出一个特殊金属 X
当
普通金属 O 的数目不足 V 时无法继续冶炼。现在给出了 N 条冶炼记录每条记录中包含两个整数 A 和 B这表示本次投入了 A 个普通金属 O最终冶炼出了 B 个特殊
金属 X。每条记录都是独立的这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。根据这 N 条冶炼记录请你推测出转换率 V 的最小值和最大值分别可能是多少题目保证评测数据不存在无解的情况。输入格式
第一行一个整数 N表示冶炼记录的数目。
接下来输入 N 行每行两个整数 A、B含义如题目所述。输出格式
输出两个整数分别表示 V 可能的最小值和最大值中间用空格分开。数据范围
对于 30% 的评测用例1≤N≤102。
对于 60% 的评测用例1≤N≤103。
对于 100% 的评测用例1≤N≤1041≤B≤A≤109。输入样例
3
75 3
53 2
59 2
输出样例
20 25
样例解释
当 V20 时有⌊7520⌋3⌊5320⌋2⌊5920⌋2可以看到符合所有冶炼记录。
当 V25 时有⌊7525⌋3⌊5325⌋2⌊5925⌋2可以看到符合所有冶炼记录。
且再也找不到比 20 更小或者比 25 更大的符合条件的 V 值了。示例代码
#include bits/stdc.husing namespace std;typedef long long LL;const int N 1e410;int n;
int a[N], b[N];bool check1(int mid) // 这里的check判断的为是否在右半边
{for(int i 1; i n; i){ // 说明在左半边if(a[i] / mid b[i]) return false; // 最小值满足条件的是右半边mid越大值越小所以当大于b[i]时就不满足条件了}return true;
}bool check2(int mid)
{for(int i 1; i n; i){if(a[i] / mid b[i]) return false; // 同理当小于b[i]时说明在右半边而二分的正确的条件应该是左半边}return true;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n;for(int i 1; i n; i) cin a[i] b[i];int r1, r2;int l 1, r 1e9; // 因为a[i], b[i]的值可能为1e9,1while(l r){ // 注意这里其实暴不了int因为就是是两个1e9也没用int mid (LL)l r 1; // 这里的check判断的为是否在右半边if(check1(mid)) r mid; // 找最小值发现右边是条件一样的所以 r midelse l mid 1;}r1 r;l 1, r 1e9;while(l r){int mid (LL)l r 1 1;if(check2(mid)) l mid; // 找最大值发现左边和自己的条件是一样的所以l midelse r mid - 1;}r2 r;cout r1 r2 endl;return 0;
}六、数的范围
标签二分
思路这道题真的写了非常多遍了但写的时候还是出错而且还把我搞迷糊了一两天导致其他的二分题都不会了都不知道怎么做了好在自己坚持慢慢耗、磨出来了知道了 c h e c k check check 函数和区间判断怎么写了思路一下子清晰了然后其余的二分题用这个方法也正确的做出来了。首先你要有个条件比如说这道题是 a [ m i d ] x a[mid] x a[mid]x然后找满足这个条件的 m i d mid mid 的最小值和最大值 然后比如说你要找 r 1 r1 r1那么和 r 1 r1 r1 满足相同条件的在 r 1 r1 r1 的右半边所以 c h e c k check check 函数为 m i d mid mid 在右半部分满足什么条件即 a [ m i d ] ≥ x a[mid] \geq x a[mid]≥x 然后因为满足条件的在右半部分所以这个条件下的语句为 r m i d r mid rmid 然后 l m i d 1 l mid 1 lmid1 这个 r m i d , l m i d 1 r mid, l mid 1 rmid,lmid1和 l m i d , r m i d − 1 l mid, r mid - 1 lmid,rmid−1都是一一对应的 c h e c k check check 条件下写前面的 e l s e else else 下写后面的然后如果是 l m i d l mid lmid 语句那么在 i n t m i d l r 1 int\ mid l r 1 int midlr1那要改成 i n t m i d l r 1 1 int\ mid l r 1 1 int midlr11否则会有边界问题。然后说一下最大值再梳理一遍其最大值满足相同条件的在左部分虽然只有一部分但只要这么想就是对的 c h e c k check check 为 a [ m i d ] ≤ x a[mid] \leq x a[mid]≤x 因为在满足条件的在左边所以 l m i d l mid lmid 然后就是 r m i d − 1 r mid - 1 rmid−1 再在二分 m i d mid mid 那加一。
题目描述
给定一个按照升序排列的长度为 n 的整数数组以及 q 个查询。对于每个查询返回一个元素 k 的起始位置和终止位置位置从 0 开始计数。如果数组中不存在该元素则返回 -1 -1。输入格式
第一行包含整数 n 和 q表示数组长度和询问个数。
第二行包含 n 个整数均在 1∼10000 范围内表示完整数组。
接下来 q 行每行包含一个整数 k表示一个询问元素。输出格式
共 q 行每行包含两个整数表示所求元素的起始位置和终止位置。如果数组中不存在该元素则返回 -1 -1。数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
输入样例
6 3
1 2 2 3 3 4
3
4
5
输出样例
3 4
5 5
-1 -1示例代码
#include bits/stdc.husing namespace std;typedef long long LL;const int N 1e510;int n, q;
int a[N];int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n q;for(int i 0; i n; i) cin a[i];while(q--){int x;cin x;int r1 -1, r2 -1;int l 0, r n - 1; // 注意看好起始位置从几开始的while(l r){int mid (LL)l r 1;if(a[mid] x) r mid; // 先看点然后看相同条件的区间在哪来判断check然后区间在右就是r midelse l mid 1; // 在左就是l mid其余的else和1跟着变就行}if(a[r] x) r1 r;l 0, r n - 1;while(l r){int mid (LL)l r 1 1;if(a[mid] x) l mid;else r mid - 1;}if(a[r] x) r2 r;cout r1 r2 endl;}return 0;
}七、最佳牛围栏
标签二分、前缀和
思路1首先这道题用了双指针跟前缀和再加上一些限制条件最大化的缩减时间然后过了 10 / 15 10/15 10/15 个数据还可以。
思路2首先这道题想着求最大平均值一般这个求最大最小的这种边界问题都可以想着用二分来做。首先是否有单调性如果假设最大平均值为 m i d mid mid 那么小于 m i d mid mid 的肯定有大于 m i d mid mid 的肯定没有所以可以通过 c h e c k check check 是否存在 m i d mid mid 来二分出来最大的 m i d mid mid 。条件就是是否存在一个长度大于等于 F F F 的连续子区间使得这个区间的平均值为 m i d mid mid 如果给每个点都减去 m i d mid mid 那么问题就等于是否存在一个长度大于等于 F F F 的连续子区间使得这个区间的和非负那么就可以用前缀和来求即 s [ j ] − s [ i ] ≥ 0 s[j] - s[i] \geq 0 s[j]−s[i]≥0即 s [ j ] ≥ s [ i ] s[j] \geq s[i] s[j]≥s[i]既然要找存在那么这个 s [ i ] s[i] s[i] 当然越小越好了就是找 i i i 之前的最小的 s [ i ] s[i] s[i] 然后用双指针算法求再处理好边界问题就行了。 模型从一段区间中找数量大于等于F的连续子区间的最大平均值
题目描述
农夫约翰的农场由 N 块田地组成每块地里都有一定数量的牛其数量不会少于 1 头也不会超过 2000 头。约翰希望用围栏将一部分连续的田地围起来并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。围起区域内至少需要包含 F 块地其中 F 会在输入中给出。在给定条件下计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。输入格式
第一行输入整数 N 和 F数据间用空格隔开。
接下来 N 行每行输入一个整数第 i1 行输入的整数代表第 i 片区域内包含的牛的数目。输出格式
输出一个整数表示平均值的最大值乘以 1000 再 向下取整 之后得到的结果。数据范围
1≤N≤100000
1≤F≤N
输入样例
10 6
6
4
2
10
3
8
5
9
4
1
输出样例
6500示例代码一 双指针、前缀和 10/15
#include bits/stdc.husing namespace std;const int N 1e510;int n, f;
int a[N], s[N];int main()
{cin n f;for(int i 1; i n; i) {cin a[i];s[i] s[i-1] a[i];}int res -2e9;for(int i 1; n - i 1 f; i){for(int j i f - 1; j n; j){res max((double)res, (double)(s[j] - s[i-1]) / (j - i 1) * 1000);}}cout res endl;return 0;
}示例代码二二分、前缀和 15/15
#include bits/stdc.husing namespace std;typedef long long LL;const int N 1e510;int n, m;
int cow[N];
double sum[N];bool check(double ave)
{for(int i 1; i n; i) sum[i] sum[i-1] cow[i] - ave;double minv 0;for(int i 0, j m; j n; i, j){minv min(minv, sum[i]);if(sum[j] minv) return true;}return false;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n m;for(int i 1; i n; i) cin cow[i];double l 0, r 2000;while(r - l 1e-5){double mid (l r) / 2;if(check(mid)) l mid;else r mid;}cout (int)(r * 1000) endl;return 0;
}
