lanqiao OJ 111 区间位移

简介: lanqiao OJ 111 区间位移

1.区间移位 - 蓝桥云课 (lanqiao.cn)

二分+贪心,  二分和贪心总是同时出现嘛  , 二分倒是简单,贪心总是很难证明也很难想到,

参考一下这两个博客

蓝桥杯历年真题——区间位移——JAVA 详解_蓝桥杯 区间位移-CSDN博客

蓝桥杯国赛第八届c++ A组 区间移位_数轴上有n个闭区间d1,…,dn。其中区间di用一对整数[ai, bi]来描述,满足ai < bi。-CSDN博客

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std ;
const int N = 1e4 + 10 ;
struct node{
  int a,b ;
  node(int aa, int bb){
    a = aa, b = bb ;
  }
};
bool cmp(node q,node w){
  return q.b < w.b ;
}
int n ;
vector<node> q ;
bool check(int mid){//先找出一个mid值
  int pos = 0 ;
  vector<node> temp(q) ;//复制原来数组,因为我们后边会对数组中的某些个点进行清楚,为了不影响下一次二分,我们用这个复制数组来操作
  while(1){
    bool flag = false ;//如果循环结束后还是false 说明区间有了不能补上的空点,如果还没有到达最后的点20000直接返回0 ;
    for(int i = 0 ; i < temp.size() ; i++ ){//从头到尾遍历每一个区间,如果又符合条件的就把这个区间放上去,对pos值进行修改
      int na = temp[i].a , nb = temp[i].b ;
      int len = nb - na ;//当前区间左端,右端,长度
      if(na - mid <= pos && nb + mid >= pos){//当前pos 在区间内,或者在移动后区间内,这样的区间符合条件
        flag = 1 ;//找到一个符合条件的区间了,进行下一次循环
        //两种情况的pos的值的更新
                if(na + mid >= pos) pos += len ; // 1.最左端移动小于等于mid就可以到达pos,那pos直接加上区间长度len
        else pos = nb + mid ;//2.最左端移动了mid了,但是还不到不了pos,就只能让去掉重复的那一块了,
        temp.erase(temp.begin()+i) ;//避免区间重复判断
        break; //找到一个符合的了,重新开始从头找
      }
    }
    if(pos>=20000 || !flag) break ;
  }
  return pos >= 20000 ;
}
int main(){
  cin >> n ;
  for(int i = 0 ; i < n ;i  ++){
    int a, b ;
    cin >> a >> b ; a*=2,b*=2 ;
    q.push_back(node(a,b)) ;
  }
  sort(q.begin(),q.end(),cmp) ; // 这是vector 的排序方法,一定要记住
  int l = 0 , r = N ;
  while(l<r){//二分
    int mid = l + r  >> 1 ;
    if(check(mid)) r = mid ;
    else l = mid + 1 ;
  }
  cout << ((double)r ) / 2 << endl ;//因为刚开是把数组都扩展了一倍,所以数组先都乘2
}
相关文章
|
2天前
|
存储 缓存 关系型数据库
MySQL事务日志-Redo Log工作原理分析
事务的隔离性和原子性分别通过锁和事务日志实现,而持久性则依赖于事务日志中的`Redo Log`。在MySQL中,`Redo Log`确保已提交事务的数据能持久保存,即使系统崩溃也能通过重做日志恢复数据。其工作原理是记录数据在内存中的更改,待事务提交时写入磁盘。此外,`Redo Log`采用简单的物理日志格式和高效的顺序IO,确保快速提交。通过不同的落盘策略,可在性能和安全性之间做出权衡。
1519 4
|
29天前
|
弹性计算 人工智能 架构师
阿里云携手Altair共拓云上工业仿真新机遇
2024年9月12日,「2024 Altair 技术大会杭州站」成功召开,阿里云弹性计算产品运营与生态负责人何川,与Altair中国技术总监赵阳在会上联合发布了最新的“云上CAE一体机”。
阿里云携手Altair共拓云上工业仿真新机遇
|
5天前
|
人工智能 Rust Java
10月更文挑战赛火热启动,坚持热爱坚持创作!
开发者社区10月更文挑战,寻找热爱技术内容创作的你,欢迎来创作!
503 19
|
2天前
|
存储 SQL 关系型数据库
彻底搞懂InnoDB的MVCC多版本并发控制
本文详细介绍了InnoDB存储引擎中的两种并发控制方法:MVCC(多版本并发控制)和LBCC(基于锁的并发控制)。MVCC通过记录版本信息和使用快照读取机制,实现了高并发下的读写操作,而LBCC则通过加锁机制控制并发访问。文章深入探讨了MVCC的工作原理,包括插入、删除、修改流程及查询过程中的快照读取机制。通过多个案例演示了不同隔离级别下MVCC的具体表现,并解释了事务ID的分配和管理方式。最后,对比了四种隔离级别的性能特点,帮助读者理解如何根据具体需求选择合适的隔离级别以优化数据库性能。
179 1
|
8天前
|
JSON 自然语言处理 数据管理
阿里云百炼产品月刊【2024年9月】
阿里云百炼产品月刊【2024年9月】,涵盖本月产品和功能发布、活动,应用实践等内容,帮助您快速了解阿里云百炼产品的最新动态。
阿里云百炼产品月刊【2024年9月】
|
21天前
|
存储 关系型数据库 分布式数据库
GraphRAG:基于PolarDB+通义千问+LangChain的知识图谱+大模型最佳实践
本文介绍了如何使用PolarDB、通义千问和LangChain搭建GraphRAG系统,结合知识图谱和向量检索提升问答质量。通过实例展示了单独使用向量检索和图检索的局限性,并通过图+向量联合搜索增强了问答准确性。PolarDB支持AGE图引擎和pgvector插件,实现图数据和向量数据的统一存储与检索,提升了RAG系统的性能和效果。
|
9天前
|
Linux 虚拟化 开发者
一键将CentOs的yum源更换为国内阿里yum源
一键将CentOs的yum源更换为国内阿里yum源
457 5
|
7天前
|
存储 人工智能 搜索推荐
数据治理,是时候打破刻板印象了
瓴羊智能数据建设与治理产品Datapin全面升级,可演进扩展的数据架构体系为企业数据治理预留发展空间,推出敏捷版用以解决企业数据量不大但需构建数据的场景问题,基于大模型打造的DataAgent更是为企业用好数据资产提供了便利。
314 2
|
23天前
|
人工智能 IDE 程序员
期盼已久!通义灵码 AI 程序员开启邀测,全流程开发仅用几分钟
在云栖大会上,阿里云云原生应用平台负责人丁宇宣布,「通义灵码」完成全面升级,并正式发布 AI 程序员。
|
25天前
|
机器学习/深度学习 算法 大数据
【BetterBench博士】2024 “华为杯”第二十一届中国研究生数学建模竞赛 选题分析
2024“华为杯”数学建模竞赛,对ABCDEF每个题进行详细的分析,涵盖风电场功率优化、WLAN网络吞吐量、磁性元件损耗建模、地理环境问题、高速公路应急车道启用和X射线脉冲星建模等多领域问题,解析了问题类型、专业和技能的需要。
2608 22
【BetterBench博士】2024 “华为杯”第二十一届中国研究生数学建模竞赛 选题分析