首页 > 其他分享 >[IOI2013]robots 机器人

[IOI2013]robots 机器人

时间:2022-10-17 16:44:05浏览次数:103  
标签:sort return IOI2013 机器人 robots mid int 数组 --

题目传送门

思路

简单题,设函数 \(f_i\) 表示当时间为 \(i\) 时是否能够收拾好所有玩具,则 \(f_i\) 显然是单调的。

所以我们可以考虑二分。

设我们当前二分到 \(x\),我们先把 \(x\) 数组按从小到大排序,\(y\) 数组按从大到小排序。

我们先扫 \(x\) 数组,假设我们当前扫到了 \(x_i\),\(1\) 至 \(j\) 的玩具可以被 \(i\) 安放,则,贪心的想,这些玩具对于 \(x\) 数组的意义是相同的,但是这些玩具的 \(s\) 值是不同的,为了尽可能存在答案,我们需要尽量给遍历 \(y\) 数组时留下尽可能小的 \(s\) 值,所以我们选取最大的 \(x\) 个 \(s\) 值删掉。

接下来扫 \(y\) 数组,每次都尽可能删去值,若最后被删空,则成立,否则不成立。

代码

#include<bits/stdc++.h>
using namespace std;
int const N=1e6+10;
int x[N],y[N],w[N],s[N],n,m,t;
struct node{int w,s;}a[N];
inline bool cmp(node x,node y){return x.w<y.w;}
inline bool check(int lim){
    priority_queue<int>q;
    int r=0;
    for (int i=1;i<=n;++i){
        while (a[r+1].w<=x[i] && r+1<=t) q.push(a[++r].s);
        int xx=lim;
        while (!q.empty() && xx--) q.pop();
    }
    while (r<t) q.push(a[++r].s);
    for (int i=1;i<=m;++i){
        if (q.empty()) break;
        if (q.top()>y[i]) return 0;
        int xx=lim;
        while (!q.empty() && xx--) q.pop();
    }
    if (!q.empty()) return 0;
    return 1;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>t;
    for (int i=1;i<=n;++i) cin>>x[i],--x[i];sort(x+1,x+n+1);
    for (int i=1;i<=m;++i) cin>>y[i],--y[i];sort(y+1,y+m+1);reverse(y+1,y+m+1);
    for (int i=1;i<=t;++i) cin>>a[i].w>>a[i].s;sort(a+1,a+t+1,cmp);
    int l=0,r=1e9;
    while (l<r){
        int mid=(l+r)>>1;
        if (check(mid)) r=mid;
        else l=mid+1;
    }
    if (l==1e9) l=-1;
    cout<<l<<'\n';
    return 0;
}

标签:sort,return,IOI2013,机器人,robots,mid,int,数组,--
From: https://www.cnblogs.com/tx-lcy/p/16799733.html

相关文章

  • 西门子PS on eMS Standalone《导入FANUC机器人TP程序》
    导入TP程序到PDPS中  右键点击左侧项目树的 “程序” -->点击 “创建TP程序”    打开示教器-->点击“SELECT”-->找到并选择创建的PROG_1-->点......
  • CF1335F Robots on a Grid
    CF1335F:因为每个格子都只向外连一条边,所以网格可感性理解为一个基环树森林。则每个机器人最终都会走到一个环上,那么所占据黑格便也在环上。那么若要使机器人数量最多,且......
  • 自主移动机器人视频分享
    自主移动机器人视频分享鱼香ROS介绍:鱼香ROS是由机器人爱好者共同组成的社区,欢迎一起参与机器人技术交流。文章信息:标题:自主移动机器人视频分享关键词:参与者:​​​小鱼......
  • 20-40K| 梅卡曼德视觉算法工程师、机器人软件、相机产品经理招聘
    3D视觉工坊致力于推荐最棒的工作机会,精准地为其找到最佳求职者,做连接优质企业和优质人才的桥梁。公司介绍梅卡曼德机器人由清华海归团队于2016年创办,致力于推动智能机器人......
  • 【每周NLP论文推荐】 开发聊天机器人必读的重要论文
    欢迎来到《每周NLP论文推荐》。在这个专栏里,还是本着有三AI一贯的原则,专注于让大家能够系统性完成学习,所以我们推荐的文章也必定是同一主题的。对于聊天机器人研究,可以追溯......
  • 基于Nonebot2搭建QQ机器人(三):插件高级
    目录Nonebot2插件高级一、工作流程1、概念2、简介3、事件处理4、调用协议端接口二、定时任务1、安装插件2、快速使用3、配置插件三、匹配规则1、创建规则2、创......
  • Jenkins 持续集成--企业微信机器人
     1、创建企微群管理机器人,获取Webhook地址 2、Jenkins--安装插件:QyWechat3、Jenkins--进入系统配置,添加默认的webhook地址系统配置  项目内实际效果 ......
  • 自动驾驶、移动机器人学习资料:定位建图、环境感知、求职
    1).机器人的带约束轨迹规划杨硕卡内基梅隆大学博士原大疆创新工程师研究方向为高自由度机器人的运动轨迹规划2).ORB-SLAM3原理与代码解析刘国庆上交感知与导航研究所科研助......
  • 推荐|一个地面机器人采集的大型数据集
    推广一下我们实验室师弟的工作:M2DGR:aMulti-modalandMulti-scenarioDatasetforGroundRobots(ICRA2022) 一个地面机器人采集的大型数据集,包括: -六个环视鱼眼相机 -......
  • 如何搭建一套免费开源的微信群机器人问答系统?
    前言自动消息回复和机器人,一直是企业微信的专利。但在非常多场景或者人文习惯中,个人微信和微信群也同样需要它们。比如活动组织者、团购团长、社群管理、私域流量运营者......