<span>cf1291c-Mind Control</span>
题意：n个数n个人依次取数，每个人只能取第一个数或最后一个数，你可以从一开始控制k个人取最前边或是最后边的数，你排在第m位，能取到的最大的数是多少。所有人取数都是最优策略（不是每次取最大数）。
题解：假设k是0，那么就是n个人，你第m个取，此时可以从0到m-1遍历表示有i个人从前边取，那么剩下的 m-1-i个人就是从后边取得，然后轮到你取得时候就是在i+1个数和n-（m-i-1）个数取最大的，从这些最大值中取最小的就是答案了；k不是0的时候，因为可以控制k个人，所以你肯定要使他们的取法最有利于你，那么，遍历从0到k表示有i个人被你控制从前边取，剩下的人从后边取，这样就变成了k是0，有n-k个数，你是第m-k-1个取，求取得的最大值，根据上边k=0的求法在所有求得的最小值中取最大值就是结果了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int a[3510]; 5 6 int main() 7 { 8 int t; 9 scanf("%d",&t); 10 while(t--){ 11 int n,m,k; 12 scanf("%d%d%d",&n,&m,&k); 13 memset(a,0,sizeof(a)); 14 for(int i=0;i<n;i++){ 15 scanf("%d",&a[i]); 16 } 17 int ans=0; 18 if(m<=k+1){ 19 for(int i=0;i<m;i++){ 20 ans=max(ans,a[i]); 21 } 22 for(int i=n-1;i>=n-m;i--){ 23 ans=max(ans,a[i]); 24 } 25 printf("%d\n",ans); 26 } 27 else{ 28 ans=0x3f3f3f3f; 29 int p=m-k; 30 if(k==0){ 31 for(int i=0;i<m;i++){ 32 int sum=0; 33 sum=max(a[i],a[n-m+i]); 34 ans=min(ans,sum); 35 } 36 printf("%d\n",ans); 37 } 38 else { 39 int q=0; 40 for(int i=0;i<=k;i++){ 41 ans=0x3f3f3f3f; 42 for(int j=i;j<p+i;j++){ 43 int sum=0; 44 sum=max(a[j],a[(n-k+i)-(p+i)+j]); 45 ans=min(ans,sum); 46 } 47 q=max(q,ans); 48 } 49 printf("%d\n",q); 50 } 51 } 52 } 53 return 0; 54 }
查看19道真题和解析