专栏首页xiaohejun的算法知识分享Codeforces_Round_616_(Div_2)_C题

Codeforces_Round_616_(Div_2)_C题

题目大意

有$n$个人,有$n$个数字组成序列$a$, 你当前站在第$m$个位置,每一次每个人从这$n$个数字的头或者尾拿走一个数字,一开始你可以说服在拿的时候$k$个人拿首还是拿尾,其他人会任意拿,说服那些人拿首还是拿尾要一开始就确定好,中间不能变。最大化通过控制能确定拿到的值

题解

注:题解描述下标从1开始,代码中下标从0开始

显然对于后$n-m$个人,他们怎么拿对结果都没有影响。那么可以说服的人数$k = min(k, m-1)$,假设说服$x$个人拿首,有$y$个没说服的人拿了首,显然$x \in [0, k],y \in [0, m-1-k]$,那么容易知道第$m$个人拿的时候,头是$a_{x+y+1}$,因为首拿了$x+y$个,尾是$a_{x+y+1+n-m}$ 因为轮到第$m$个人拿的时候,还有$n-m+1$个数字,那么$z-(x+y+1)+1=n-m+1$,解得$z=x+y+1+n-m$。所以暴力枚举$x$和$y$的值就得到一个$O(n^2)$的算法。最终答案如下

$$b_i=max(a_{1+i}, a_1+i+(n-m))$$

$$ans = max_{x \in [0, k]}\lbrace min_{y \in [0, m-1-k]}b_{x+y} \rbrace$$

# def wrapper(func):
#     def inner():
#         return next(func)
#     return inner
# input = wrapper(open('in.txt'))

T = int(input())
for case in range(T):    
    n, m, k = map(int, input().strip().split())
    a = list(map(int, input().strip().split()))
    k = min(m-1, k)
    ans = 0
    for x in range(k+1):
        res = int(2e9)
        for y in range(m-k):
            res = min(res, max(a[x+y], a[x+y+n-m]))
        ans = max(ans, res)
    print(ans)
'''

'''

令$y’=x+y$,上面的式子可以变化为

$$ans = max_{x \in [0, k]}\lbrace min_{y’ \in [x, x+m-1-k]}b_{y’} \rbrace$$

所以上面的式子可以用线段树来计算,复杂度是$O(nlogn)$,由于求区间最小值的时候区间长度是$m-k$不变的,所以还可以用单调队列来做(和LeetCode的这道题目差不多239. Sliding Window Maximum),复杂度是$O(n)$,下面是单调队列的做法:

# def wrapper(func):
#     def inner():
#         return next(func)
#     return inner
# input = wrapper(open('in.txt'))

import collections

T = int(input())
for case in range(T):    
    n, m, k = map(int, input().strip().split())
    a = list(map(int, input().strip().split()))
    k, b = min(m-1, k), []
    for i in range(m):
        b.append(max(a[i], a[i+n-m]))
    ans = 0
    d = collections.deque()
    for i in range(m): 
        while d and b[i] <= b[d[-1]]:
            d.pop()
        while d and (i-d[0]+1 > m-k):
            d.popleft()
        d.append(i)
        if i >= m-k-1:
            ans = max(ans, b[d[0]])
    print(ans)
'''

'''

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Educational_Codeforces_Round_81(Rated_for_Div. 2)_D题

    求$gcd(a, m) = gcd(a+x, m), 0 <= x < m, 1 <= a < m <= 10^{10}$的$x$的个数

    xiaohejun
  • AtCoderBeginnerContest112

    题目大意: 输入1的时候输出”Hello World”. 输入2的时候会输入a,b.计算a+b.

    xiaohejun
  • 算法竞赛入门经典训练指南打卡day1

    题解: 转换一下问题.每一个流星在矩形照相机中的时间段是确定的(如果可以进入矩形照相机).假设在这n个流星中有k个流星在一定时间段可以照到.第$i$个流星能照到...

    xiaohejun
  • ASP.NET MVC 开源项目Kigg解读(2)——Kigg.Core第一部分

    Kigg是一个很好的ASP.NET MVC范例项目,本着研究的目的,对Kigg进行解读。 上一篇中,我们介绍了Kigg的启动、后台任务和事件聚合器。这一篇,我们...

    用户1177380
  • 在VMware虚拟机软件中安装的Ubuntu虚拟机的窗口不能自动调整大小的解决办法

    在 VMware虚拟机软件 中安装的 Ubuntu虚拟机 的窗口不能自动调整大小的解决办法:

    黑泽君
  • WebGL简易教程(一):第一个简单示例

    不得不说现在三维图形渲染技术更新换代实在是太快,OpenGL很多资料还没来得及学习就已经有点落伍了。NeHe的学习教程还有之前用的《OpenGL编程指南》第七版...

    charlee44
  • 备胎的养成记KeepAlived实现热备负载

      在  入坑系列之HAProxy负载均衡 中已经详细讲过了怎么将高并发的请求按均衡算法分发到几台服务器上做均衡防止单机崩溃。   但这样的话有没有发现所有请求...

    欢醉
  • iOS:键盘中文限制

    菜菜不吃蔡
  • Java虚拟机-03:当new一个对象时,虚拟机发生了什么?

    Java是一门面向对象的编程语言,在Java程序运行的过程当中,随时都会有对象创建出来,从语言层面上来讲,创建对象通常仅仅是使用一个new关键字而已,那在...

    IT云清
  • 如何在CRM WebClient UI里创建HANA live report

    The three parameters are defined as mandatory in HANA studio )

    Jerry Wang

扫码关注云+社区

领取腾讯云代金券