首页 > Present
开通博客写题解
头像 __故人__
发表于 2020-09-14 15:07:22
分析 经典的字眼，要求最小值最大。考虑二分答案。如何判断合法性。对于二分出来的最小值。从左向右扫一次，在考虑 时，我们已经保证 是一个合法的区间了，所以只有向后加才有意义。所以遇到小于二分出来的数时，直接 这个区间 。用差分数组维护一下就好了，当操作次数大于 时是不合法答案，时间复杂度为 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 又在摸鱼的大熊猫很勤奋努力
发表于 2020-09-14 15:02:59
Present 题目大意: 先给你一串序列,你至多有次操作使得一段长度为的区间加一问这串序列的最小值最大可以是多少? 分析: 最小值最大或者最大值最小,我们的第一反应可能都是二分答案 简单证明一下: 如果最小值最大为,那么只要我们少做一次操作,那么也是可行的这满足二分答案的性质,所以呢二分答案没 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 Dear㉿You
发表于 2020-09-20 07:57:35
前言 刚开始什么思路都没有，但是突然想到了一道题——换教室，似乎也是二分，然后运用到这一道题，似乎就明了了 分析 这道题的话，通过二分最小的w，是每一盆花的a[i]>=w，并且浇的天数小于等于m。这就是主要思路。 实现 题目中给出了一个w(刚开始我也不知所措啊QwQ)，然而我们想一想 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 DeNeRATe
发表于 2020-09-15 11:39:21
分析 由于我们需要求出最后序列最小值最大所以我们直接可以想到二分答案经验告诉我们，我们需要先考虑比较特殊的数列位置从最左边开始考虑若果当前不成立，那么我们将他加到成立为止并是以当前位置为起点的向后加1所以我们需要的是区间修改，单点查询可以的树状数组当然更可以的差分可以证明这种贪心是绝对最优的需要注意 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 Kur1su
发表于 2020-09-17 20:37:30
Description Little beaver is a beginner programmer, so informatics is his favorite subject. Soon his informatics teacher is going to have a birthday a 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 熠丶
发表于 2020-09-17 16:38:40
做法：二分+差分 思路： 最小值最大化-->二分然后利用差分来进行二分操作，具体见check函数代码 代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) ma 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 嘻嘻嘻嘻嘻嘻嘻
发表于 2020-09-15 14:35:21
题目：https://ac.nowcoder.com/acm/problem/110615题意：给定a数组，可操作m次让w个连续的位置+1，问最大化的最小值是多少。分析： 明显，最小值越大越难满足，满足单调性，考虑二分； check就从前往后考虑当前位置是否满足最小，不满足则选择以当前位 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 程序蒟蒻
发表于 2020-09-18 10:36:29
二分答案，设当前答案为x，也就是碉值最低的话的碉值最大值为x。从头到尾观察花，若a[i]<x，则对a[i]开头的w盆花怒浇(x-a[i])天，让其碉值达到x。让所有的a[i]都>=x。若怒浇的天数和小于等于m，则可行。可以用差分队列实现因为差分数列b[i]=a[i]-a[i-1]，则当前 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 issue是云哥的小迷×呀
发表于 2020-10-04 15:32:22
最小值最大,果断二分 二分之后就是裸题了 遇到第一个不满足二分值的必须要加了,而且是从这个位置开始加 维护用差分就好了 看代码吧,这个没什么好说的 #include <bits/stdc++.h> using namespace std; #define int long long co 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”