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

【管道——二分+区间合并】

题目

思路

  • 区间合并
    • 1、按照左端点排序
    • 2、遍历窗口,若窗口非法,继续遍历;否则执行3
    • 3、若是第一个窗口,设定合并结果初值,判断结果左端点是否造成“起点过大”,是,FALSE退出;否则执行4
    • 4、判断合并是否会造成“中间缺失”,是,FALSE退出;否,执行5
    • 5、更新结果右端点
    • 6、判断结果右端点是否造成“终点过小”,是,FALSE退出;否则执行2
    • 7、TRUE退出

代码

#include <bits/stdc++.h>
using namespace std;
#define L first
#define S second
const int N = 1e5 + 10;
const int M = 1e9;
typedef pair<int, int> PII;
typedef long long ll;
PII win[N];
int n, len;
ll mid;
ll getl(PII a)
{
  return (ll)a.L - mid + a.S;
}
ll getr(PII a)
{
  return (ll)a.L + mid - a.S;
}
bool cmp(PII a, PII b)
{
  //[L-T+S,L+T-S]
  return getl(a) < getl(b);
}
bool check()
{
  sort(win + 1, win + n + 1, cmp);

  ll l = 0, r = 0;
  for (int i = 1; i <= n; i++)
  {
    ll nl = getl(win[i]), nr = getr(win[i]);
    if (nl > nr)
      continue; // 无效
    if (r == 0)
    {
      l = nl;
      r = nr;
      if (l > 1)
        return false; // 起点过大,无法覆盖
      continue;
    }
    if (nl - r > 1) // 中间缺少,无法覆盖
      return false;
    r = max(r, nr); // 取大
  }

  if (r < len)
    return false; // 终点过小,无法覆盖
  return true;
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> len;
  for (int i = 1; i <= n; i++)
  {
    cin >> win[i].L >> win[i].S;
  }
  ll l = 0, r = 2 * M;
  while (l < r)
  {
    mid = l + r >> 1;
    if (check())
      r = mid;
    else
      l = mid + 1;
  }

  cout << l;
}


http://www.kler.cn/a/467314.html

相关文章:

  • 《C++11》各种初始化方式的详细列举与对比
  • Windows提示msvcp120.dll丢失怎么解决?Windows文件丢失的4种解决方法,教你修复msvcp120.dll文件
  • iOS - 线程与AutoreleasePoolPage
  • nginx学习之路-nginx配置https服务器
  • RK3588+麒麟国产系统+FPGA+AI在电力和轨道交通视觉与采集系统的应用
  • 一文大白话讲清楚TCP连接的三次握手和断开连接的四次挥手的原理
  • .Net加密与Java互通
  • Ubuntu静态IP地址
  • HTML——78. 图像地图
  • 【AWS SDK PHP】This operation requests `sigv4a` auth schemes 问题处理
  • 常见的 MySQL 性能问题
  • 框架Tensorflow2
  • 《Rust权威指南》学习笔记(四)
  • Elasticsearch:Lucene 2024 年回顾
  • 豆包 MarsCode 编程助手之Visual Studio Code快速开始教程
  • 【数据可视化-10】国防科技大学录取分数线可视化分析
  • SQL Server 数据库 忘记密码
  • 5.1 冒泡排序与选择排序
  • 对一个双向链表,从尾部遍历找到第一个值为x的点,将node p插入这个点之前,如果找不到,则插在末尾。使用C语言实现
  • Unity3D仿星露谷物语开发16之角色拾取道具
  • spark环境搭建
  • T-SQL语言的编程范式
  • 如何不修改模型参数来强化大语言模型 (LLM) 能力?
  • 【Unity笔记】如何把语言修改为简体中文?
  • 全国青少年信息学奥林匹克竞赛(信奥赛)备考实战之循环结构(for循环语句)—(十)(求解数学中特殊的数)
  • windows终端conda activate命令行不显示环境名