首页 > 其他 > 详细

CodeForces - 1290A - Mind Control(思维)

时间:2020-04-27 17:26:44      阅读:32      评论:0      收藏:0      [点我收藏+]

题目链接OvO

题目大意

??有一个长度为\(n\)的序列,每个人都能拿走序列中的第一个数或者最后一个数,你可以指定\(k\)个人拿的顺序,问第\(m\)个人拿的数最大是多少。

分析

??既然这个题的数据不大那么就尽可能的往暴力的方面想,有没有办法列举出所有的情况呢?先看一下下图:
??技术分享图片
??可以很容易的看出,对于选定\(k\)个之后可选的区间会是一个长度为\(n-k\)的滑块,我们要做的就是枚举出滑块里面所有的情况,再让滑块移动,改变区间,再进行枚举,那么滑块里面是什么情况呢?
??技术分享图片
??在黑滑块里面还有一个红色子滑块,这个子滑块的头尾两个数之间的最大值就是每种情况要选的数(因为要最优所以选最大的)。而这个滑块可以移动的范围就是选完\(k\)个之后到\(m\)之间的那几个数,因为这几个选择是不能指定的,所以对于一个固定的黑滑块来说,其最优的情况就是所有最优解的最小值。而对于整个序列来说,因为前\(k\)个人是可以指定的,所以最优解就是所有最优解最小值中的最大值。

具体实现

??实现上没什么好说的,主要是计算方面可能有点问题。首先需要注意的是如果\(k\)大于\(m-1\)的话取\(m-1\)就行了,再大了也不会对结果又影响而且实现起来还会带来麻烦。然后就是注意一下计算各个滑块长度与可移动距离的大小就行了。

代码

const int maxn = 1e4+10;
int arr[maxn];
int main(void) {
    int t;
    cin >> t;
    while(t--) {
        int n, m, k;
        cin >> n >> m >> k;
        for (int i = 1; i<=n; ++i) cin >> arr[i];
        if (k>=m) k = m-1;
        int ans = -1, len1 = n-k, len2 = len1-(m-k-1);
        for (int i = 1; i<=k+1; ++i) {
            int tmp = INF;
            for (int j = i; j<=i+m-k-1; ++j)
                tmp = min(tmp, max(arr[j], arr[j+len2-1]));
            ans = max(ans, tmp);
        }
        cout << ans << endl;
    }
    return 0;
}

CodeForces - 1290A - Mind Control(思维)

原文:https://www.cnblogs.com/shuitiangong/p/12787918.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!