二分例题(D.负重越野,I.路径规划)

2024-05-27 22:52

本文主要是介绍二分例题(D.负重越野,I.路径规划),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这两天的训练赛都有一道二分的题,但是都没往二分上面想,同样不知道怎么二分。

D. Fast and Fat

思路

二分的关键也就是check函数怎么写了,求队伍最大速度,可以分为速度>=mid和<mid两部分,再判断,能不能实现速度大的背小的,并且速度>=mid.

代码

#include<bits/stdc++.h>
using namespace std;
# define int long long
int n;
struct pi{int v,w;
}a[100005];
bool cmp1(pi a,pi b)
{return a.v+a.w>b.v+b.w;
}
bool cmp2(pi a,pi b)
{return a.w>b.w;
}
int check(int x)
{vector<pi> s;//存放速度小的,需要被背着vector<pi> q;//存速度大的,for(int i=1;i<=n;i++){if(a[i].v>=x)q.push_back(a[i]);else s.push_back(a[i]);}if(q.size()<s.size())return 0;sort(q.begin(),q.end(),cmp1);//速度可能会变为vi+wi-wj,所以按vi+wi的大小顺序排sort(s.begin(),s.end(),cmp2);//w从大到小排。//无需考虑太多,如果最大的vi+wi去背wj,速度达不到,那也不用考虑其他的了,必须要保证每个小的都被背for(int i=0;i<s.size();i++){if(q[i].v+q[i].w-s[i].w<x)return 0;}return 1;
}
void solve()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i].v>>a[i].w;int l=-1,r=1e9+10;while(l<r)//这是小于等于最大值的二分{int mid=(l+r+1)>>1;if(check(mid))l=mid;else   r=mid-1;	}cout<<l<<'\n';
}
signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie();int t;cin>>t;while(t--){solve();}
}

I. Path Planning

思路

用一个map,键存位置,值存数字,关于check函数,我一直想的都是i,j,i+j…但这些其实可以不考虑,要满足向右下走,用两重循环,i的值在不断增大,此时已经是向下,这时只需要,设个变量判断j,就可以了

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
map<pair<int,int>,int> ma;
int n,m;
int check(int x)//这样判断很巧妙,而且首尾数字是什么,都无关紧要
{int k=0;for(int i=1;i<= n;i++)for(int j=1;j<= m;j++)//如果是一行或一列,不需要特殊考虑,因为j逐步增大{if(ma[{i,j}]<x){if(j<k) return 0;k=j;}}return 1;
}
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>ma[{i,j}];//这里将map和pair结合,赛时也没想到int l=0,r=n*m;while(l<r){int mid=l+r+1>>1;if(check(mid))l=mid;else 	r=mid-1;	}cout<<l<<'\n';
}
signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--){solve();}
}

这篇关于二分例题(D.负重越野,I.路径规划)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1008827

相关文章

SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志

《SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志》在SpringBoot项目中,使用logback-spring.xml配置屏蔽特定路径的日志有两种常用方式,文中的... 目录方案一:基础配置(直接关闭目标路径日志)方案二:结合 Spring Profile 按环境屏蔽关

VSCode设置python SDK路径的实现步骤

《VSCode设置pythonSDK路径的实现步骤》本文主要介绍了VSCode设置pythonSDK路径的实现步骤,包括命令面板切换、settings.json配置、环境变量及虚拟环境处理,具有一定... 目录一、通过命令面板快速切换(推荐方法)二、通过 settings.json 配置(项目级/全局)三、

使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)

《使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)》字体设计和矢量图形处理是编程中一个有趣且实用的领域,通过Python的matplotlib库,我们可以轻松将字体轮廓... 目录背景知识字体轮廓的表示实现步骤1. 安装依赖库2. 准备数据3. 解析路径指令4. 绘制图形关键

如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)

《如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)》:本文主要介绍如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)问题,具有很好的参考价值,希望对大家有所帮助,如有... 目录先在你打算存放的地方建四个文件夹更改这四个路径就可以修改默认虚拟内存分页js文件的位置接下来从高级-

一文详解如何查看本地MySQL的安装路径

《一文详解如何查看本地MySQL的安装路径》本地安装MySQL对于初学者或者开发人员来说是一项基础技能,但在安装过程中可能会遇到各种问题,:本文主要介绍如何查看本地MySQL安装路径的相关资料,需... 目录1. 如何查看本地mysql的安装路径1.1. 方法1:通过查询本地服务1.2. 方法2:通过MyS

Python如何调用指定路径的模块

《Python如何调用指定路径的模块》要在Python中调用指定路径的模块,可以使用sys.path.append,importlib.util.spec_from_file_location和exe... 目录一、sys.path.append() 方法1. 方法简介2. 使用示例3. 注意事项二、imp

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使