搜索
房产
装修
汽车
婚嫁
健康
理财
旅游
美食
跳蚤
二手房
租房
招聘
二手车
教育
茶座
我要买房
买东西
装修家居
交友
职场
生活
网购
亲子
情感
龙城车友
找美食
谈婚论嫁
美女
兴趣
八卦
宠物
手机

【做题笔记】 P1610 鸿山洞的灯

[复制链接]
查看: 95|回复: 0

1万

主题

1万

帖子

4万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
45261
发表于 2020-2-14 22:30 | 显示全部楼层 |阅读模式
正解:DP
比力好写的/我用的算法:贪心
首先需要明白几个地方:

  • 第二行输入的 \(n\) 个数字是每盏灯地点的地方。可以不顺顺序,灯与灯之间的间隔是个变量
  • 对于尽情一段区间,只如果在 \(\text{dist}\) 的范围内,可以封闭多盏灯
贪心计谋:首先排序,然后循环 \(2\) ~ \(n-1\) ,由于第一盏和末端一盏不能关。若前后满足条件,则将第 \(i\) 盏与第 \(i-1\) 盏交换。这样覆盖了当前灯,也就相当于“关灯”。下一次比力时,相当于仍然在与第 \(i-1\) 盏灯比力(即可行区间,可以绘图明白)。若在某一时候不合适条件,则自动比力另一组数据。按此方式处置赏罚,时候复杂度 \(O(n)\) ,可 \(\text{AC}\) 。
完整代码以下:
[code]#include #include #include using namespace std;int n,d,a[100001],ans;int main(){    scanf("%d%d",&n,&d);    for(int i=1;i
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Copyright © 2006-2014 全椒百姓网-全椒知名**,发布及时新鲜的全椒新闻资讯 生活信息 版权所有 法律顾问:高律师 客服电话:0791-88289918
技术支持:迪恩网络科技公司  Powered by Discuz! X3.2
快速回复 返回顶部 返回列表