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

炼石#8 T1

image
image

赛时很快想出切掉,感觉比t2恶心🤢,可能是二分做法的问题(bushi
想法简单,贪心想法保留m个最小的 ,于是二分k用来区分大数和小数 , 如果小于k/2为小数 , 显然小数是必拿 ,然后在每个小数之间最多只能有一个大数,且需要满足小数加这个大数小于k即可
然后如果最后长度小于m就找大,大于等于m就找小细节看注释

#include <bits/stdc++.h>  // 包含所有标准库头文件,方便快速编写代码
#define MAXN 500010       // 定义宝石数量的最大上限
#define inf 2000000000    // 定义二分查找的右边界(足够大的数)
#define int long long     // 将int类型重定义为long long,避免整数溢出
using namespace std;namespace SHuxinn {int n, m, a[MAXN];  // n:原项链的宝石总数;m:需要保留的宝石数;a[]:存储每块宝石的破碎值vector<int> s;      // 存储满足「a[i] ≤ 当前二分的k/2」的宝石位置(用于辅助判断相邻和)// 检查:当最大允许的相邻宝石破碎值之和为k时,能保留的宝石数量是否 ≥ mint check(int k) {s.clear();  // 每次检查前清空容器for (int i = 1; i <= n; i++) {// 筛选出「自身破碎值 ≤ k/2」的宝石(这类宝石更容易与其他宝石相加不超过k)if (a[i] <= k / 2) {s.push_back(i);}}if (s.empty()) {  // 若没有宝石满足「a[i] ≤ k/2」,则任意两块相加都>k,最多只能留1块return 0;}if (s.size() == 1) {  // 只有1块满足「a[i] ≤ k/2」的宝石,检查是否能找到另一块与之相加≤kint l = s[0];for (int i = 1; i <= n; i++) {if (i != l && a[i] + a[l] <= k) {  // 找到不同的宝石且和≤kreturn 2;  // 能保留2块}}return 1;  // 找不到,只能保留1块}int last = 0;   // 记录上一个「a[i] ≤ k/2」的宝石位置int ans = 0;    // 记录在「a[i] ≤ k/2」的宝石之间,额外能保留的宝石数量int r = s.size() - 1;  // 环形结构中,最后一个「a[i] ≤ k/2」的宝石在s中的索引for (auto l : s) {  // 遍历所有「a[i] ≤ k/2」的宝石位置if (last == 0) {  // 处理第一个「a[i] ≤ k/2」的宝石(环形的“开头”情况)// 取「当前宝石」和「最后一个满足条件的宝石」的较大值(因为是环形,首尾相邻)int maxx = max(a[l], a[s[r]]);bool vis = 1;  // 标记是否在“首尾之间”找到可保留的宝石// 检查「第一个满足条件的宝石」左边的宝石(环形的左半部分)for (int j = 1; j < l && vis; j++) {if (maxx + a[j] <= k) {  // 找到能与maxx相加≤k的宝石ans++;  // 保留这块宝石vis = 0;  // 标记已找到,退出循环}}// 检查「最后一个满足条件的宝石」右边的宝石(环形的右半部分)for (int j = s[r] + 1; j <= n && vis; j++) {if (maxx + a[j] <= k) {  // 找到能与maxx相加≤k的宝石ans++;  // 保留这块宝石vis = 0;  // 标记已找到,退出循环}}last = l;  // 更新上一个满足条件的宝石位置为当前lcontinue;}// 处理非第一个「a[i] ≤ k/2」的宝石(检查当前l与上一个last之间的宝石)int maxx = max(a[last], a[l]);  // 上一个和当前满足条件的宝石的较大值for (int i = last + 1; i < l; i++) {if (maxx + a[i] <= k) {  // 找到中间能保留的宝石ans++;  // 保留这块宝石break;  // 只要找到一个就停止(尽可能多保留,找到即满足)}}last = l;  // 更新上一个满足条件的宝石位置}// 总保留数 = 满足「a[i] ≤ k/2」的宝石数 + 中间额外保留的宝石数return s.size() + ans;}void Sx5() {int tid;cin >> tid >> n >> m;  // 输入:测试点编号、原宝石数n、需要保留的宝石数mint maxx = 0;for (int i = 1; i <= n; i++) {cin >> a[i];        // 输入每块宝石的破碎值maxx = max(maxx, a[i]);  // 记录最大的破碎值(二分初始参考)}// 二分查找:最小的「最大相邻和」int l = 0, r = inf, ans;  // l:左边界;r:右边界;ans:最终答案while (l <= r) {int mid = (l + r) / 2;  // 当前猜测的「最大相邻和」if (check(mid) >= m) {  // 若能保留至少m块宝石r = mid - 1;        // 尝试更小的「最大相邻和」ans = mid;          // 记录当前可行的答案} else {l = mid + 1;        // 否则需要更大的「最大相邻和」}}cout << ans << endl;  // 输出最小的「不美观度」(即最小的最大相邻和)}
}signed main() {freopen("necklace.in", "r", stdin);   // 重定向输入到文件necklace.infreopen("necklace.out", "w", stdout); // 重定向输出到文件necklace.outSHuxinn::Sx5();  // 调用命名空间内的核心逻辑函数return 0;
}

ps::注释是ai写的只粗略的看了一眼,有问题欢迎纠正

http://www.hskmm.com/?act=detail&tid=21630

相关文章:

  • 详细介绍:《C++ Primer Plus》读书笔记 第二章 开始学习C++
  • 【虚拟机】“:域名解析出现暂时性错误”VMware配置DNS
  • 双抗 ADC:如何突破传统 ADC 瓶颈,成为癌症治疗的精准杀伤利器?
  • 微信聊天记录移动到外置磁盘后,如何解决无法引导聊天记录
  • AI+手搓第一个AI Agent“AI胜铭兰”
  • 基于JDK17的GC调优策略
  • 【MC】我的世界schematic方块坐标提取转为json
  • Jenkins+IIS+Bonobo.Git.Server 搭建适用dotnet开发者的小团队的devops环境
  • JDK17新特性梳理
  • 完整教程:Nginx 高级配置指南:Rewrite、If判断、浏览器分离与防盗链
  • 数据结构学习随笔 第一章
  • 函数-参数+作用域
  • 用 Nim 实现英文数字验证码识别
  • 抓紧上车,别再错过啦, Github 开源后台管理平台,Naive UI !!!
  • 深入解析:【网络编程】套接字入门:网络字节序与套接字种类剖析
  • 地产行业,居然还有这样的开发商 - 智慧园区
  • Tita项目与绩效一体化管理:重构组织效能的数字化中枢
  • 实用指南:电子电气架构 --- 智能座舱域环境感知和人机交互系统
  • 强化学习(二十二)-MADDPG
  • GLM-4.6与DeepSeek-V3.2-Exp发布
  • 2025.9.30——1黄
  • 【半导体物理 | 笔记】第二章 半导体中杂质和缺陷能级
  • 基于内容可信空间的医疗行业机遇研究报告
  • v-show会导致重绘还是重排?
  • M3-Agent:看见、听见、记住与推理:具备长期记忆的多模态智能体
  • 20250930
  • 阿里云发布《AI 原生应用架构白皮书》
  • NVR接入录像回放平台EasyCVR智慧农田可视化视频监控方案
  • sql server 版本查询
  • Matlab dsp工具箱可以实现定点FFT的功能