[CF1534G]A New Beginning

news/2024/4/16 3:29:16

A New Beginning

题解

吐槽一下官方题解,当谜语人吗?

蒟蒻的做法是从诸位的代码中学习来的,大部分人的代码都好像呀,由于没找到一篇题解,所以就自己从代码中臆想了一下方法

我们很容易发现,对于对于点 i i i,路径上最优的一个匹配点一定有一个是在点 i i i所在的对角线 x + y = x i + y i x+y=x_{i}+y_{i} x+y=xi+yi上的。

假设我们在点 ( a , b ) ( a + b < x + y ) (a,b)(a+b< x+y) (a,b)(a+b<x+y),对于点 ( x , y ) (x,y) (x,y),我们现在的代价为 m a x ( ∣ x − a ∣ , ∣ y − b ∣ ) max(|x-a|,|y-b|) max(xa,yb)

a < x , b < y a<x,b<y a<x,b<y时,无论怎么走都不会变得更劣。

a < x , b > y a<x,b>y a<x,b>y时,由于 x − a > b − y x-a>b-y xa>by,所以只有当我向下走的时候会变得更优,而向右走在到达对角线之前 b − y b-y by即使增大,也一直是小于 x − a x-a xa的,不会变得更劣。

a > x , b < y a>x,b<y a>x,b<y时同理。

而当我们的 a + b > x + y a+b>x+y a+b>x+y时,也就是我们已经走过了对角线,

image-20210619151643342

我们只能向右或向下走,但很明显,我们怎么也走不到代价更小的地方了。

所以可以发现,我们在对角线上时肯定是代价最小的。

由于我们每走一步只会让 x + y x+y x+y的和增加 1 1 1,所以我们的路径与 x + y = x i + y i x+y=x_{i}+y_{i} x+y=xi+yi肯定是有交点的。

但我们又该去怎么求总代价最小的路径呢?

首先是很容易考虑到 d p dp dp的,我们先将 ( x i , y i ) (x_{i},y_{i}) (xi,yi)按照 x i + y i x_{i}+y_{i} xi+yi的大小排序,设 d p i dp_{i} dpi表示在 x = i x=i x=i的点的最小代价。

走到 ( x k , y k ) (x_{k},y_{k}) (xk,yk)对应的对角线时,有转移
d p i = min ⁡ ∣ j − i ∣ ⩽ ( x k + y k − x k − 1 − y k − 1 ) ( d p j + ∣ x k − i ∣ ) dp_{i}=\min_{|j-i|\leqslant(x_{k}+y_{k}-x_{k-1}-y_{k-1})}(dp_{j}+|x_{k}-i|) dpi=ji(xk+ykxk1yk1)min(dpj+xki)
很明显,直接这样转移的时候是 O ( 1 0 9 n ) O\left(10^9n\right) O(109n)的,不可能过得了。

我们可以寻找一下它转移的性质。

首先最优值肯定可以出现在一个已出现点对应的某个点(即它会在层与层之间向右或向下走到的点)上的。

我们可以先将新加入的点分成 3 3 3类,太左边以至于走不到,太右边以至于走不到,走得到。

image-20210619161927408

这里用颜色区别开了。

我们假设 S S S的左边还有一些点,但它们没有 S S S优秀。

如果我接下来加入的点是在中央区域,这只会导致左边的相对差距增大,增大的值就是它们之间的相对距离。

但由于新加入的点可以由原来的最优点走到,原来的最优点又增大了,所以新点的值就是最优的了。它们之间的差距就是它们的相对距离。

如果加入的新点在蓝色区域,那么在新点左边与右边的点的 d p dp dp值都会增大。都是离新点越远增大的越多,增大的都是它们间的相对距离。

此时对于右边的点,就会产生变动了,如果最优点与次优点之间的差距只有它们之间的相对距离,那么此时的最优点就变成原来的次优点了。原来的最优点无论如何都不会在另一个新最优点出现之前变得比它更优。

如过新加入的点在红色区域呢?很显然,这只会继续让它们的相对差距增加。

对于在 S S S右边的点同理。

于是,我们想到可以维护两个优先队列。

一个表示左边部分的最优选择,其中最优点是最队列中最靠右的点。另一个表示右边的最优选择。

由于在这个对角线上,从左到右 x x x是递增的,从右到左 y y y是递增的,一个就按 x x x排序,一个按 y y y排序。

优先队列中往后的点与前面的点的差距与前面的点数有关,当这个点前面没有点时,它就是最优的了。

加入点时有如下三种情况。

  • 如果加入的点在红色区域就往两个队列中各加入一个点,最优值没有变化。

  • 如果加入的点在蓝色区域就找到 x x x对应队列的最优点,向里面加入两个新点,并将原来的最优点删除,最优值增加原来最优点与新点的差距。

    如果原来的最优点有两个就说明它与后面的还有差距,它本身还是最优的,否则它就与下一个是相同的没用了。

但很明显,我们发现原来的最优点现在对于 y y y的那个序列还是有影响的,它会变成 y y y序列中的最优点,并加大 y y y间的相对差距。

所以我们还要填一个步骤。

  • 并将这个最优点加入 y y y的队列中。
  • 如果原来加入的点在红色区域,由于 x x x轴与 y y y轴是等价的,翻一翻也没问题,所以它们的操作应该也是相似的,只是对 y y y序列进行 x x x的操作罢了。

这样的时间复杂度是 O ( n l o g n ) O\left(nlog\,n\right) O(nlogn)

源码

其实代码挺简单的。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 800005
#define lowbit(x) (x&-x)
#define reg register
#define mkpr make_pair
#define fir first
#define sec second
typedef long long LL;
typedef unsigned long long uLL;
const int INF=0x3f3f3f3f;
const int mo=1e9+7;
const int iv2=5e8+4;
const int lim=1000000;
const int jzm=2333;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
typedef pair<int,int> pii;
const double PI=acos(-1.0);
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int add(int x,int y){return x+y<mo?x+y:x+y-mo;}
int n,sum;LL ans;pii a[MAXN],b[MAXN];
bool cmp(pii x,pii y){return x.fir+x.sec<y.fir+y.sec;}
priority_queue<pii>qx,qy; 
signed main(){read(n);for(int i=1;i<=n;i++)read(a[i].fir),read(a[i].sec);sort(a+1,a+n+1,cmp);for(reg int i=1;i<=n;i++)b[i]=mkpr(a[i].sec,a[i].fir);qx.push(a[1]);qy.push(b[1]);for(reg int i=2;i<=n;i++){if(qx.top().fir>a[i].fir){pii t=qx.top();int dif=t.fir-a[i].fir;ans+=1ll*dif;qx.pop();qy.push(mkpr(a[i].sec-dif,a[i].fir+dif));qx.push(a[i]);qx.push(a[i]);}else if(qy.top().fir>b[i].fir){pii t=qy.top();int dif=t.fir-b[i].fir;ans+=1ll*dif;qy.pop();qx.push(mkpr(b[i].sec-dif,b[i].fir+dif));qy.push(b[i]);qy.push(b[i]);}else qx.push(a[i]),qy.push(b[i]);}printf("%lld\n",ans);return 0;
}

谢谢!!!


http://www.ppmy.cn/news/291975.html

相关文章

Ubuntu cmake 编译环境搭建及编译方法 (lesson 01)

Linux cmake 使用方法 下载cmake 并安装第一个程序 下载cmake 并安装 下面展示一些操作 内联代码片。 sudo apt-get update sudo apt-get install cmakeloveubuntu:~$ cmake Usagecmake [options] <path-to-source>cmake [options] <path-to-existing-build>Spec…

apple 西单大悦城维修_如何检查Apple是否已召回MacBook(免费维修)

apple 西单大悦城维修 Apple 苹果 Apple has recalled a lot of MacBooks recently. Your MacBook may be eligible for free replacement of its battery, keyboard, logic board, display backlight, or another component. Here’s how to check whether you can get some f…

vue使用高德地图--附带移动获取当前城市信息

高德地图 1.使用准备申请密钥vue使用 2.移动地图获取城市案例(注意事项)3.总结 1.使用准备 申请密钥 登录注册高德开放平台进入控制台 创建应用 申请key–生成key和安全密钥(2021之后key需要配合安全密钥使用) 注意&#xff1a;安全密钥需要在key之前 vue使用 首先在pubil…

CISP-PTE2022最新考试经验分享

CISP_PTE2022年10月份考试心得体会 2022年9月份由于公司需要&#xff0c;参加了中启航的CISPPTE培训&#xff0c;总培训时间八天&#xff0c;8师傅讲的很好&#xff0c;浅显易懂&#xff0c;经过4天的理论学习和4天的实操练习&#xff0c;经过十一假期的熟练&#xff0c;我在10…

【深入浅出 Spring Security(七)】RememberMe的实现原理详讲

RememberMe 的实现原理 一、RememberMe 的基本使用二、RememberMeAuthenticationFilter 源码分析RememberMeServicesTokenBasedRememberMeServicesTokenBasedRememberMeServices 中对 processAutoLoginCookie 方法的实现总结原理图式 三、提高安全性PersistentTokenBasedRememb…

基于Tensorflow+SDD+Python人脸口罩识别系统(深度学习)含全部工程源码及模型+视频演示+图片数据集

目录 前言总体设计系统整体结构图系统流程图 运行环境Python 环境Anaconda 环境搭建 模块实现1. 数据预处理2. 模型构建及算法实现3. 模型生成 系统测试1. 训练准确率2. 运行结果 工程源代码下载其它资料下载 前言 在当今全球范围内&#xff0c;新冠疫情对我们的生活方式带来了…

linux命令输出结果但不显示在屏幕上的通用办法

linux命令输出结果但不显示在屏幕上的通用办法 这个针对于我这种小白马大哈很简单的一个命令&#xff0c;记给自己备用 举个例子&#xff1a;unzip命令不输出结果 unzip xx.zip > /dev/null 2>&1 unzip xx.zip > /dev/null 前半部分是将标准输出重定向到空设备…

计算机能安装几个硬盘,一台电脑最多能接多少个硬盘?

一台电脑最多能接多少个硬盘&#xff0c;主要还是要看电脑主板硬盘接口的数量&#xff0c;由于m.2或msata接口会占用sata接口&#xff0c;一般电脑最多可以接多少块硬盘取决于电脑主板可独立使用的硬盘接口数。需要注意的是&#xff0c;如果电脑连接多个硬盘&#xff0c;需要机…

WPS免费账号分享(WPS会员+稻壳会员)

办公用到wps会员&#xff0c;随手开了个&#xff0c;用的不多&#xff0c;分享给大家一起用。 超级会员&#xff1d;wps会员稻壳会员&#xff0c;一般的功能应该都有了。加水印、转换pdf、简历模板、ppt模板、excel模板等 另外给大家分享15天稻壳的领取方法和pdf转word、exce…

硬盘2.5寸4tb服务器硬盘,西部数据My Passport 2.5英寸4TB移动硬盘

购买理由 楼主有两个黑群晖的服务器&#xff0c;其中一个服务器专门用于保存重要的影像资料。虽然楼主为这个重要的服务器配备了UPS&两块4T红盘做raid1进行保护&#xff0c;但楼主有被害妄想症&#xff0c;生怕出什么意外事件&#xff0c;尤其是在红盘的质量堪忧的现状下&a…

Easyrecovery2022硬盘磁盘U盘免费数据恢复软件

EasyRcovery的软件支持因各种原因损坏或误删的文件&#xff0c;文档&#xff0c;照片&#xff0c;视频&#xff0c;音频&#xff0c;电子邮件等等类型的数据它都可以恢复。同时&#xff0c;这款软件不仅仅支持u盘的数据恢复&#xff0c;移动硬盘&#xff0c;磁盘&#xff0c;sd…

保姆级给电脑分盘,和合并两个盘

保姆级给电脑分盘&#xff0c;和合并两个盘 分盘 第一步 找到我的电脑&#xff0c;右击选择管理&#xff0c;进入管理&#xff0c;点击存储&#xff0c;再点击硬盘管理 第二步 选中你要分的盘&#xff0c;右击选择压缩卷在输入压缩空间量中输入你要的大小比如&#xff1a;64G…

电脑硬盘一共有多少种

硬盘接口分ide sata scsi三种 一般ide和sata是用在普通的Pc机上而scsi是用在服务器上 ide的传输速率为133mb/s称为并口 sata-i传输速率为150mb/s称为串口 sata-2传输速率为300mb/s scsi你没有提到俺就不说了&#xff01; 下面的是我给你找则参考资料 ide的英文全称为“int…

有什么好用的通用型项目管理软件

目前市面上的项目管理产品非常丰富&#xff0c;在选择项目管理软件的过程中一一了解这些产品哪个更好更适合自己的团队&#xff0c;无疑会浪费很多时间成本。通用性项目管理工具可以满足大部分团队的项目管理需求&#xff0c;那有什么好用的通用型项目管理软件呢&#xff1f;知…

这里推荐几个前端icon网站(动图网站)

1. Loading.ioLoading.io 是一个免费的加载动效(Loading animations)图标库。它提供了多种风格的加载动效图标,包括 SVG、CSS 和 Lottie 动画格式。这些加载图标可以增强用户体验,为网站和应用程序添加更佳的视觉效果。 网站地址:loading.io - Your SVG GIF PNG Ajax Loading…

强大工具推荐,APP爬虫采集与逆向必备清单

正所谓工欲善其事&#xff0c;必先利其器&#xff01; 移动应用的快速发展和广泛普及带来了海量的数据&#xff0c;这些数据对于市场分析、用户行为洞察和业务优化具有重要价值。然而&#xff0c;由于移动应用的特殊性和防护措施&#xff0c;传统的爬虫技术在采集移动应用数据方…

在webpack中使用Eslint

一、Eslint介绍 要在webpack中使用Eslint首先我们先了解下什么是Eslint 1. 什么是Eslint ESLint是一个用于在JavaScript代码中发现和报告问题的静态代码分析工具。它可以检测常见的编码错误&#xff0c;如拼写错误、变量未声明、使用未定义的变量等&#xff0c;还可以检测代…

美的业绩逆势增长,格力下滑并失去空调霸主之位

国内三大家电企业均公布了2020年的业绩&#xff0c;其中家电双雄美的和格力的空调霸主之争尤为受人关注&#xff0c;业绩显示美的空调业务营收已超过了格力&#xff0c;这是格力首次在年度空调收入方面败给美的。 美的和格力此消彼长 美的公布的业绩显示&#xff0c;2020年取得…

传感器-陀螺仪芯片

https://www.cnblogs.com/tomatokely/p/16392997.html 陀螺仪芯片厂家&#xff1a; ST ICM42605, MPU 6050, Murata SCL3300/3400 陀螺仪可选量程&#xff1a; 15.6/31.2/62.5/125/250/500/1000/2000 dps 加速度可选量程&#xff1a; 2/4/8/16 g 计算单位&#xff1a; 陀…

h5故障代码_美的空调故障代码h5 看完你就知道了

操作方法 01 空调没有“h5”故障代码&#xff0c;故障代码“hs”常被人误认为“h5”&#xff0c;故障代码“hs”表示空调正在自动除霜&#xff0c;正好是化霜的首拼。这空调在制热时常见的现象&#xff0c;并不是空调出现故障而且空调系统程序中本来就有的&#xff0c;每个型号…
最新文章