当前位置: 首页 > news >正文

CF1832D2 Red-Blue Operations (Hard Version) 模拟赛题目分析

CF1832D2 Red-Blue Operations (Hard Version)

题目概述

给你 \(\{a_n\}\),第 \(i\) 次操作,如果是你第奇数次操作当前位置则令它 \(+i\) 否则 \(-i\)

给出 \(q\) 个询问,问你进行完 \(k\) 个操作之后 \(a\) 中的最小值最大是多少?

题目分析

这道题目一眼二分答案。

先对 \(a\) 排序。

观察题目性质(经典):

  • 对于当前位置 \(x\),如果我在 \(i\) 的时候操作了一次,那么我下一次一定会操作它,这样会使得代价最小(只减少 \(1\))。

因为我们考虑的是二分答案,所以说只需要确定对于每一个 \((k,val)\) 去检查 \(k\) 步能不能实现全部都大于等于 \(val\)

首先确定 \(k\) 的下界。

对于第 \(i\) 个数,我们想要将它变到大于等于 \(x\),于是有:

\[a_i+k-i+1\geq x \]

移项得到:

\[k\geq c+(i-1-a_i) \]

为什么呢,因为我肯定是对于小的那个给予最大的关怀。

取前缀最大值即可。

这个我门直接找 \(<val\) 即可。

\(k=2w+p\),我们假设后面用 \(p\) 次加,那么显然,这 \(p\) 个可以加进去,这个我们可以假定 \(p\)\(<val\) 的个数,然后如果奇偶性不同,则让 \(p+1\) 即可。

如果说 \(k\) 比下界小,那就不行,如果说 \(p\) 进行 \(+1\) 之后若 \(>n\) 就不行,因为此时判的情况就是 \(p=n\) 时但奇偶性不同所以说就会再减了一次。

还需要判断 \(k\) 的上界。

显然只需要满足:

\[sum-n\times val+(k+k-1+\dots+k-p+1)>w \]

其意义时总和减去下面都有的部分,再加上一开始加的部分,这些部分就是我要可能减去的部分,如果这个部分不够减,那不好意思,就不行。

然后就能 AC 了。

代码

时间复杂度 \(\mathcal{O}(q\log V\log n)\)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#define int long long
#define N 200005
using namespace std;
int n,q,sum;
int a[N],lim[N];
bool check(int k,int c) {int p = lower_bound(a + 1,a + n + 1,c) - a - 1;if (p == 0) return true;if (k < p) return false;if ((k - p) & 1) p ++;if (p > n) return false;if (k < c + lim[p]) return false;if (sum * 2 - n * c * 2 + p * (2 * k - p + 1) >= k - p) return true;return false;
}
signed main(){cin >> n >> q;for (int i = 1;i <= n;i ++) scanf("%lld",&a[i]),sum += a[i];stable_sort(a + 1,a + 1 + n);for (int i = 1;i <= n;i ++) lim[i] = i - a[i] - 1;for (int i = 2;i <= n;i ++) lim[i] = max(lim[i],lim[i - 1]);for (int i = 1;i <= q;i ++) {int k;scanf("%lld",&k);int l = 0,r = 1e18,res = 0;while(l <= r) {int mid = l + r >> 1;if (check(k,mid)) res = mid,l = mid + 1;else r = mid - 1;}printf("%lld ",res);}return 0;
}
http://www.hskmm.com/?act=detail&tid=27508

相关文章:

  • 网络流最小割,无向图建图法,求最小割点转换求最小割边
  • 实验1 C语言开发环境使用和数据类型、运算符、表达式
  • 深度学习概述 - -一叶知秋
  • 烧录神器来了!量产工具使用教程,新手也能秒懂
  • 看论文随笔Incendio: Priority-Based Scheduling for Alleviating Cold Start in Serverless Computing
  • C#性能优化基础:内存诊断(dump)
  • 2025年企业级LLM内容安全防护指南:鉴冰AI FENCE流式网关技术深度解析
  • 完整教程:FPGA学习笔记——图像处理之亮度调节(Gamma)
  • Kubernetes Ingress:管理集群外部访问的入口网关
  • 搜索选讲
  • vue打包的项目,从根目录进去路由可访问,浏览器直接打开这个路由不可访问
  • IObit Uninstaller一款强大的卸载工具!IObit Uninstaller卸载工具,IObit Uninstaller下载安装教程
  • 网络配置不再难:4G/Wi-Fi/以太网/虚拟网卡全指南
  • 计算几何
  • 2025开关按钮厂家最新推荐榜:开关按钮,带灯开关按钮,防水开关按钮,防爆开关按钮,防腐开关按钮等全种类覆盖,高品质设计与卓越性能口碑之选
  • 一种排查java.lang.OutOfMemoryError: Metaspace的方法
  • First Blog Post
  • 本站点即将在2025年改变研究方向和目标
  • 实用指南:12_OkHttp初体验
  • (AE)Adobe After Effects 2025 视频后期制作软件!安装包永久免费免激H解锁版下载与图文详细安装教程!!
  • Postgresql主从配置
  • 乒乓球
  • 2025年工程管理软件系统推荐榜:交付管理/工程协同/工程管理/智慧工地管理系统
  • 《程序员修炼之道》 阅读笔记一
  • 大型行为模型LBM超越语言模型的技术解析
  • 2025工程管理软件系统推荐榜:技术赋能下的场景化解决方案全景
  • 【LVS入门宝典】LVS-TUN模式原理与配备:跨越网络界限的负载均衡解决方案
  • Java基础-Eclipse工具-面向对象(1)
  • Avalonia UI 投资 Wilderness Labs
  • BLE开发新体验:四种模式全解析,源码免费开放