cf1291c-Mind Control

题意：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 }

巴特西

cf1291c-Mind Control

最新文章

热门文章