深信服四道编程题

偏执的太偏执、 2022-05-09 23:14 159阅读 0赞

## 一、木板最大接水量 ##

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");
        		 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");
        		 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);
    
    	}
    
    }