算法题分析

╰半橙微兮° 2022-06-05 03:20 122阅读 0赞

【题目描述】  
在主城站街很久之后，小萌决定不能就这样的浪费时间虚度青春，他打算去打副本。  
这次的副本只有一个BOSS，而且BOSS是不需要击杀的，只需要和它比智力…….  
BOSS会列出一正整数的序列，由小萌先开始，然后两个人轮流从序列的任意一端取数，取得的数累加到积分里，当所有数都取完，游戏结束。  
假设小萌和BOSS都很聪明，两个人取数的方法都是最优策略，问最后两人得分各是多少。  
输入  
第一行：一个正整数N（2 ≤ N ≤ 100），表示序列中正整数的个数。  
第二行至末尾：用空格隔开的N个正整数（1 ≤ a\[i\] ≤ 200）  
输出  
只有一行，用空格隔开的两个数，小萌的得分和BOSS的得分。  
样例输入  
6  
4 7 2 9 5 2  
样例输出  
18 11

上面的题目，在一个讨论组看到后自己写一个自己想的解法。

package com.demo;
    
    public class Main { 
        public static void main(String[] args) {
            int[] a ={
       4,7,2,9,5,2};//输入数据
            int PA=0,PBOSS=0;//Pa表示挑战者，PBoss表示Boss
            int[] indexArray = toIndexArray(a);
            boolean tt =false;
            int flag = (indexArray.length&0x001 )== 1?(indexArray.length>>1)+1:(indexArray.length>>1);
            for(int i=0;i<indexArray.length;i++){
                if(i<flag){
                    if(indexArray[i]==-1){
                        PA+=a[2*i];
                        tt=true;
                    }else{
                        if(!tt){
                            PA+=a[2*i+indexArray[i]];
                            PBOSS+=a[2*i+1-indexArray[i]];
                        }else{
                            PA+=a[2*i-1+indexArray[i]];
                            PBOSS+=a[2*i-indexArray[i]];
                        }
                    }
                }else{
                    if(indexArray[i]==-1){
                        PBOSS+=a[2*i];
                        tt=true;
                    }else{
                        if(!tt){
                        PBOSS+=a[2*i+indexArray[i]];
                        PA+=a[2*i+1-indexArray[i]];}
                        else {
                            PBOSS+=a[2*i-1+indexArray[i]];
                            PA+=a[2*i-indexArray[i]];
                    }
                    }
                }
            }
            System.out.println("PA"+PA);
            System.out.println("PBOSS"+PBOSS);
        }
        /** *设置一个数组，返回每两个数中最大的数坐标，第一个数大那就是返回0否者返回1，如果数组长度是奇数，到了中间数不比较，直接设置为-1，并且把步长i-1.继续每两个数比较。下面算法用了一些小的技巧 */
        public static int[] toIndexArray(int[] a){
            int ban =a.length>>1;//
            boolean b = (a.length&0X0001) ==1?true:false;
            int[] c;
            if(b){
                c= new int[ban+1];
            }
            else {
                c=new int[ban];
            }
            if(b){
                int ban2 =ban>>1;
                for(int i=0,j=0;i<a.length;i=i+2,j++){
                    if((ban&0x001)==1){
                        if(i==ban+1){
                            c[j]=-1;
                            i--;
                            continue;
                        }
                        if(a[i]>=a[i+1]){
                            c[j]=0;
                        }
                        else{
                            c[j]=1;
                        }
                    }else{
                        if(i==ban){
                            c[j]=-1;
                            i--;
                            continue;
                        }
                        if(a[i]>=a[i+1]){
                            c[j]=0;
                        }
                        else{
                            c[j]=1;
                        }
                    }
                }
            }else{
                for(int i=0,j=0;i<a.length;i=i+2,j++){
                    if(a[i]>=a[i+1]){
                        c[j]=0;
                    }
                    else{
                        c[j]=1;
                    }
                }
            }
            return c;
        }
    
    }