深信服四道编程题

一、木板最大接水量

import java.util.Scanner;
import java.util.Stack;
/**
木板接水
*/
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();     //t组测试用例
        while (t > 0) {
            int n = sc.nextInt();   //t个木板
            int[] lenArr = new int[n];
            for (int i = 0; i < n; i++) {
                lenArr[i] = sc.nextInt();
            }

            int ans = 0;
            Stack<Integer> maxIndexStack = new Stack<>();
            for (int i = 0; i < n; i++) {
                while ((maxIndexStack.size() > 1) && lenArr[maxIndexStack.peek()] <= lenArr[i]) {
                    maxIndexStack.pop();
                }

                if (maxIndexStack.size() == 1 && lenArr[maxIndexStack.peek()] <= lenArr[i]) {
                    int index = maxIndexStack.pop();
                    ans += (i - index) * lenArr[index];
                }

                maxIndexStack.push(i);
            }

            while (maxIndexStack.size() > 1) {
                int index = maxIndexStack.pop();
                ans += (index - maxIndexStack.peek()) * lenArr[index];

            }
            System.out.println(ans);

            t--;
        }

    }

}

二、信服下午茶

import java.util.*;

//求水果和面包的单价
public class Main {


   public static void main(String[] args) {
     Scanner sin=new Scanner(System.in);
     int n=Integer.valueOf(sin.nextLine());
     while(n>0)
     {
         long a1=sin.nextLong();
         long b1=sin.nextLong();
         long c1=sin.nextLong();
         long a2=sin.nextLong();
         long b2=sin.nextLong();
         long c2=sin.nextLong();
         if(a1*b2-b1*a2==0)
         {
             System.out.println("UNKNOWN");
             n--;
             continue;
         }
         long x= (c1*b2 - c2*b1)/(a1*b2 - a2*b1);
         long y=(c1*a2 - c2*a1)/(b1*a2 - b2*a1);
         if(x<0||y<0||a1*x+b1*y!=c1)
         { 
             System.out.println("UNKNOWN");
             n--;
             continue;
         }
         System.out.println(x+" "+y);
         n--;
     }        
  }
}

三、最小子序列和

import java.util.*;

public class Main {
   //最小的子序列和
  public static int minSubSum(int[] a){
        int minSum=Integer.MAX_VALUE,sum=0;
        for(int i=0;i<a.length;i++){
            sum+=a[i];
            if(minSum>sum){
                minSum=sum;
            }else if(sum>0){
                sum=0;
            }
        }
        return minSum;
    }

   public static void main(String[] args) {
     Scanner sin=new Scanner(System.in);
     int len=Integer.valueOf(sin.nextLine());
     int[]arr=new int[len];
     for(int i=0;i!=len;i++)
          arr[i]=sin.nextInt();
     System.out.println(minSubSum(arr));

  }
}

四、最大岗位效益安排

public class Main {
    public int process(int cur, int[] job, int[][] matrix) {
        if (cur == matrix.length) {
            return 0;
        }

        int[] job1 = new int[job.length];
        int[] job2 = new int[job.length];
        for (int i = 0; i < job.length; i++) {
            job1[i] = job[i];
            job2[i] = job[i];
        }

        // 不选岗位
        int max1 = process(cur + 1, job1, matrix);

        // 选个岗位
        int max2 = 0;

        for (int col = 0; col < job2.length; col++) {
            int tmp = 0;
            if (job2[col] > 0) {
                job2[col]--;
                tmp = matrix[cur][col] + process(cur + 1, job2, matrix);
                job2[col]++;
            }
            max2 = Math.max(max2, tmp);

        }

        return Math.max(max1, max2);

    }

}