Codeforces #366 (Div. 2) D. Ant Man (贪心)
2024-08-26 23:42:54
https://blog.csdn.net/liangzhaoyang1/article/details/52215276 原博客
原来好像是个dp题,不过我看了别人的博客使用贪心做的 复杂度(n^2)
题意:在一个数轴上有n个点,每个点有5个值x,a,b,c,d,你每次可以从一个点i跳跃到另外一个点j。
如果j在i的右边,则需要花费abs(x[i]-x[j])+c[i]+b[j]。
如果j在i的左边,则需要花费abs(x[i]-x[j])+d[i]+a[j],
一开始你位于s点,你的目的是遍历所有的点1遍并且最后停在e点,求最小花费.(注意:每个点最多只能遍历1遍)
题解:
初始化链:next[s] = e表示直接从起点s跳到终点e。
然后枚举其他所有的点,将它们一个一个插入到链中(寻找加入到链中的什么地方花费最低)
例如样例:
①:初始化:4->3
②:插入编号为1的点,显然1只能插入一个地方,插入后:4->1->3
③:插入编号为2的点,2可以插入两个地方(4和1中间或1和3中间),可以轻松算出插入4和1中间成本更低,所以
插入后:4->2->1->3
④:编号为3和4的点是起点和终点,跳过
⑤:插入编号为5的点,5可以插入三个地方,其中插入1和3中间成本更低,插入后:4->2->1->5->3
⑥:插入编号为6的点,……,插入后:4->2->1->6->5->3。
代码中的实现:
用 dis函数处理距离。
对 i=1~n按顺序 插,碰到s和e就跳过。 对每一个i,都找到一个最恰当的插的位置k,处理 k和前后的关系。
花费 用t表示,在计算t的时候 要减去原来dis(u,next[u]),这样后面直接就可以 ans+=minn。
#include<iostream>
#include<cstdio>
#include <cctype>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<cmath>
#include<set>
#include<vector>
#include<stack>
#include<queue>
#include<map>
using namespace std;
#define ll long long
#define mem(a,x) memset(a,x,sizeof(a))
#define se second
#define fi first
const int INF= 0x3f3f3f3f;
const int N=3e5+; int n,s,e;
ll x[],a[],b[],c[],d[];
ll net[]; ll dis(int l,int r)
{
if(l<r) return abs(x[l]-x[r])+d[l]+a[r];
if(l>r) return abs(x[l]-x[r])+c[l]+b[r];
} int main()
{
cin>>n>>s>>e;
for(int i=;i<=n;i++) scanf("%lld",&x[i]);
for(int i=;i<=n;i++) scanf("%lld",&a[i]);
for(int i=;i<=n;i++) scanf("%lld",&b[i]);
for(int i=;i<=n;i++) scanf("%lld",&c[i]);
for(int i=;i<=n;i++) scanf("%lld",&d[i]); net[s]=e;
ll ans=dis(s,e);
for(int i=;i<=n;i++)
{
if(i==s||i==e) continue; int u=s;
ll minn=1e18;
int k;
while(u!=e)
{
ll t=dis(u,i)+ dis(i,net[u])- dis(u,net[u]);
if(t<minn)
{
minn=t;
k=u;
}
u=net[u];
}
ans+=minn;
//接下来把i插入这个线性结构中
net[i]=net[k]; //把i插在k的后面,k的next 就变成了 i的next
net[k]=i; //k的next变成 i
}
cout<<ans;
}
最新文章
- 个人对B/S项目的一些理解(一)
- NSString 初始化方法的内存比较
- 2016年最佳Linux发行版排行榜
- Spring(1)
- 虚拟机安装Ubuntu到U盘
- Hyper-V初涉:功能的添加与虚拟机的创建
- Stream Player control
- 使用VS Code 开发.NET Core 应用程序 部署到Linux 跨平台
- springmvc请求参数异常处理
- 数据采集:完美下载淘宝Ip数据库 简单的程序节省60元人民币而不必购买数据库
- BUAA1389愤怒的DZY(最大值最小化)
- Write operations are not allowed in read-only mode
- Unix守护进程
- mongoDB启动参数备忘
- 新唐M0特点分析
- EF 数据库迁移(Migration)
- 关于Android 7.0(API24)相机的问题汇总
- sqlzoo:3
- Elasticsearch-6.7.0系列-Joyce博客总目录
- windows修复分区卷:chkdsk
热门文章
- eNSP——实现OSPF与ACL综合实验
- 解决Ubuntu14.04不能打正确拼音--无法选择第二个拼音
- Ubuntu中Qt Creator无法启动调试
- [转帖]Linux内核系统体系概述
- 计算机网络自顶向下方法第3章-传输层 (Transport Layer).2
- ArcGIS SOE开发异常之 ClassFactory cannot supply requested class
- 编译内核提示mkimage command not found – U-Boot images will not be built
- 用ASP.NET Web API技术开发HTTP接口(一)
- dotnet core2.2 通过虚拟机发布到CentOS上
- eigenface算法笔记