Mind Control

题目链接

Solution

假设被你控制的人里有i个人选最前面的，那么到你可能出现的情况就是从 以i+1~i+m-k个数开头的连续n-m+1个数，这时，你一定会从两端的数字中选一个最大的，即每种可能的情况你的选择都是确定的，那么这些情况下可选的最小值就是一种控制下的答案 $ ans_i \(，再找出最大的\) ans_i $就是答案。
枚举所有可能的情况，即需要枚举i，j(j=i+1~i+m-k),时间复杂度为O(n^2).

code（bipartite graph）

#include<bits/stdc++.h>

using namespace std;

int T,n,m,k,ar[3555],cnt,dis[3555],ans,del[3555];
struct node
{
    int nm,id,p;
}mayb[3555];

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        memset(ar,0,sizeof(ar));
        memset(mayb,0,sizeof(mayb));
        memset(dis,0,sizeof(dis));
        ans=0;cnt=0;
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=n/2+1;i++)dis[i]=dis[n+1-i]=i;
        for(int i=1;i<=n;i++)scanf("%d",&ar[i]);
        for(int i=1;i<=m;i++)
        {
            if(ar[i]>ar[i+n-m])
            {
                mayb[++cnt].id=i;
                mayb[cnt].nm=ar[i];
                mayb[cnt].p=i;
            }
            else if(ar[i]<ar[i+n-m])
            {
                mayb[++cnt].p=i+n-m;
                mayb[cnt].id=i+n-m;
                mayb[cnt].nm=ar[i+n-m];
            }
            else
            {
                mayb[++cnt].id=i;
                mayb[cnt].nm=ar[i];
                mayb[cnt].p=i+n-m;
            }
        }
        k=min(k,m-1);
        for(int i=0;i<=k;i++)
        {
            int b=1e9;
            for(int j=i+1;j<=m-k+i;j++)
            {
                if(mayb[j].id<=i || mayb[j].p>=n+1-(k-i))continue;
                else b=min(b,mayb[j].nm);
            }
            ans=max(ans,b);
        }
        printf("%d\n",ans);
    }
}