codeforce 1290A-Mind Control【思维】

题意：

  一串数共 $n$n个，排成一列，有 $n$n个人对数进行操作，每次去数列的第一个或最后一个。现在你的位置是第 $m$m个，并且你可以控制任意 $k$k 个人的选择。问你所能取到的最大的数的最小值是多少？
<mark>关键还是在于思考的角度！</mark>
  由于有些人是不能控制的，所以他们的选择的所有情况都要考虑。
  如果 $k>=m-1$k>=m−1 ,那么最终结果是可以控制的。否则，就要枚举所有情况。
假设能控制的 $k$k 个人中去前面的有 $x$x 人，不能控制的人中去前面的有 $y$y 人。所以此时，我所能取得数的最大值即为 :
$max\left(a\right[x+y+1],a[n-(k-x)-(m-1-k-y)\left]\right)$max(a[x+y+1],a[n−(k−x)−(m−1−k−y)])
复杂度： $O\left(n^2\right)$O(n2)

#include <bits/stdc++.h>
using namespace std;
const int N=3600;
int a[N];
int main()
{
    int t,n,m,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        k=min(m-1,k);
        int op=m-1-k;
        int ans=0;
        for(int i=0;i<=k;i++)//可控求最大
        {
            int res=0x3f3f3f3f;
            for(int j=0;j<=op;j++)//不可控求最小
            {
                int t=max(a[i+j+1],a[n-(k-i)-(op-j)]);//两端取最大
                res=min(res,t);
            }
            ans=max(ans,res);
        }
        printf("%d\n",ans);
    }
    return 0;
}

还可以用双端队列求：（题解的代码，没怎么看懂）

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    k = min(k, m - 1);
    vector<int> a(n);
    for(auto &x : a)
        cin >> x;
    vector<int> b;
    for(int i = 0; i < m; i++)
        b.push_back(max(a[i], a[i + n - m]));//距两端的距离和为m，所有情况所能取得到的值
    int sz = m - k;
    int ans = 0;
    deque<int> q;
    for(int i = 0, j = 0; i + sz - 1 < m; i++) {
        while(q.size() && q.front() < i)
            q.pop_front();
        while(j < i + sz) {
            while(q.size() && b[q.back()] >= b[j])
                q.pop_back();
            q.push_back(j++);
        }
        ans = max(ans, b[q.front()]);
    }
    cout << ans << '\n';
}

int main() {
    int t;
    cin >> t;
    while(t--)
        solve();
    return 0;
}