竞赛讨论区 > 【每日一题】2021年4月22日题目精讲

【每日一题】2021年4月22日题目精讲

头像
是筱筱呀
编辑于 2021-04-23 14:58:10 APP内打开
赞 0 | 收藏 0 | 回复4 | 浏览463

题号 NC51187
名称 环路运输
来源 0x55 动态规划-环形与后效性处理
每日一题三期汇总贴~
图片说明
如果你在题库做题时遇到了喜欢的题目,欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿,投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励,可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解


作者: jzdx(hjh)

算法

(单调队列)

环的处理

对于环形问题我们有一个定式:将环断开然后得到一条链,复制一遍接到链尾得到一个长为2N的序列

这样做的一个好处就是,在这样一条长度为的序列中,任意一个长度为的连续序列都对应到

环从某一位置断开并展开后得到的序列


试着思考公式转化

如果我们能将公式中的同类项和并,比如将合并起来,将合并起来考虑

每次枚举都是定值,这时只需要维护一个的最值就可以求解答案

但是中含有绝对值符号使得我们并不能轻易的将分离

但是如果我们按照上述方法得到一个长度为的序列后我们发现代价的公式可以作如下转化

 

其中:

 环

 长为2N的序列

我们很容易发现后件的表达式的答案构成的集合和前件表达式的答案构成的集合是相同的

所以我们只需要计算第二个表达式的最大值即可

然而我们发现由于i和j的前面的符号是不确定的所以我们还是无法合并

进一步思考一下公式中的是否是必要的呢?

对于环上的两点,他们顺时针的距离加上逆时针的距离之和必定是环的周长

所以

  1. 对于奇数环,较短的那个路径的距离一定是小于环周长的一半
  2. 对于偶数环,较短的那个路径的距离一定是小于等于周长的一半

所以公式还可以进一步转化

其中


求解答案

我们合并同类项 = 

每次枚举 ,对于而言是定值,所以我们只需要找到一个最大的即可

我们发现,永远在一个长度为的区间中,滑动窗口最大值可以用单调队列来优化

维护全局最大值

枚举,当大于时用单调对列更新答案

最后输出res

时间复杂度 

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 2000010;
int q[N];
LL a[N];
int n;

int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%lld",&a[i]);
        a[i + n] = a[i];//破环成链
    }
    LL res = 0;
    int hh = 0,tt = -1;
    for(int i = 1;i <= n * 2;i ++)
    {
        if(hh <= tt && i - q[hh] > n / 2) hh ++;
        if(i >= n + 1) res = max(res,a[i] + a[q[hh]] + i - q[hh]);
        while(hh <= tt && a[q[tt]] - q[tt] <= a[i] - i) tt --;
        q[++ tt] = i;
    }
    printf("%lld\n",res);
    return 0;
}

欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!


活动奖励:

牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目4月29日中午12:00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴

4条回帖

回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐