NOIP2018&2013提高组T1暨洛谷P5019 铺设道路
2024-10-02 05:42:33
题目链接:https://www.luogu.org/problemnew/show/P5019
花絮:普及蒟蒻终于A了一道提高的题目?emm,写一篇题解纪念一下吧。求过!
分析:
这道题我们可以采用一种略带数学&贪心的思想来解决,其实也可以使用差分,但并没有必要了。因为任何一个点都可以单独减1。
我们可以遍历每个点,然后发现当后一个点b的值大于前一个点的值时,我们需要把b减去前面的那个值(或再之前的),来实现最优解。
因为我们发现,要最短的天数就必须每天最长的修理距离,最长的修理距离也就是要保证前几天施完工后给这一天留下的最长。
然后问题差不多就解决了。
如有问题,欢迎私信讨论。
放代码
代码:
#include<cstdio>
using namespace std;
int a[100005];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
int ans=0,tmp=0,last=0;
for(int i=1;i<=n;i++)
{
if(a[i]>a[i-1])
{
ans+=tmp-last;
tmp=a[i];
last=a[i-1];
}
}
ans+=tmp-last;
printf("%d",ans);
return 0;
}
最新文章
- S5中新增的Array方法详细说明
- ComponentOne Xuni助力Xamarin开发者突破百万,快速开发Android、IOS Apps
- react native TypeError network request failed
- PHP操作MongoDB学习(转)
- hdu 2709 Sumsets
- 缩小jquery体积
- 正确设置网站title、keywords、description(转载)
- C#共享内存实例 附源码
- php获取二维数组中某一列的值集合
- 用Python写一个贪吃蛇
- Django 之 流程和命令行工具
- Android--加载大分辨率图片到内存
- 每日一练ACM 2019.0422
- 「JLOI2015」骗我呢 解题报告?
- C# 简单学习正则表达式
- Python源码文件中带有中文时,输出乱码
- 解决 ModuleNotFoundError: No module named &#39;pip&#39;
- mysql实战优化之九:MySQL查询缓存总结
- java 序列化与解序列化
- 新开篇关于vue
热门文章
- Android零基础入门第79节:Intent 属性详解(上)
- Git基本用法(一)
- 任何一件事,如果你不投入时间和精力去驯养,就不可能产生真正的兴趣和热爱(Focus Feedback FixIt的原理) good
- Hadoop 三剑客之 —— 分布式计算框架 MapReduce
- Flutter学习笔记(2)--Dart语言简介
- eclipse中junit简单使用
- 使用elasticsearch启动项目报错failed to load elasticsearch nodes 。。。。。No type specified for field [name]
- Node中的cookie的使用
- python算法与数据结构-二叉树的代码实现(46)
- K Balanced Teams CodeForces - 1133E (Dp)