字节跳动笔试第一题：田忌赛马

贪心问题：田忌赛马

package bytedance0721;
import java.util.Scanner;
import java.util.Arrays;
public class TianJiSaiMa {
	/** * 贪心问题：田忌赛马 * 先将双方的马按从小到大排序，总是以当前双方最慢的马进行比较 * 1.如果田忌手上最慢的马大于齐王手上最慢的马，赛一把，胜利加1 * 2.如果田忌手上最慢的马小于齐王最慢的马，那么此马必输，让其与齐王最好的马比赛，失败+1 * 3.如果田忌最慢的马等于齐王最慢的马，要讨论此时是平局（反而是下下策），还是去赛齐王最好的马？ * 因为如果田忌后面的马队友有可能战胜当前齐王最慢的马，自己与齐王最好的马比，输一场，队友赢一场，与打平受益一样， * 同时还给了自己最好马胜利的几率（齐王最好的马跟你这个菜鸡比赛了），那么自己的输也会给己方多赢一把争取机会。 * 选择自己输之前，要判断己方最好的马是否能战胜齐王最好的马， * 如果己方的最好马一顿操作猛如虎，那么没你这个最慢马什么事了，选择平局就OK * */

	 public static void main(String[] args) {
		 Scanner in = new Scanner(System.in);
		 int n = in.nextInt();
		 int[] tSpeed = new int[n];
		 int[] qSpeed = new int[n];
		 for(int i=0;i<n;i++) {
			 tSpeed[i] = in.nextInt();
		 }
		 for(int i=0;i<n;i++) {
			 qSpeed[i] = in.nextInt();
		 }
		 int num = process(tSpeed,qSpeed);
		 System.out.println(num);
	 }
	 
	 public static int process(int[] a,int[] b) {
		 Arrays.sort(a);
		 Arrays.sort(b);
		 int i =0, j=0,sum=0;
		 int len1 = a.length-1, len2 = a.length-1;
         while(i<=len1 && j<=len2) {
        	 if(a[i]>b[j]) { //田忌最慢马比齐王最慢马要快
        		 i++;
        		 j++;
        		 sum++;
        	 } else if(a[i]<b[j]) {// 田忌最慢马比齐王最慢马要慢，田最慢对齐最快
        		 i++;
        		 len2--;
        		 sum--;
        	 } else {
        		 if(i!=len1) { // 当前最慢马不是最后一匹马
        			 if(a[len1]>b[len2]) { 
        				 len1--;
        				 len2--;
        				 sum++;
        			 } else { // 放水，最慢挑最快
        				 i++;
        				 len2--;
        				 sum--;
        			 }
        		 } else { // 最后一场了，平手
        			 i++;
        			 j++;
        		 } 
        	 } 
         }
		 return sum;
	 } 
	
}

测试：

4
70 55 50 20
70 65 55 20