Сравните 2 силы команды и найдите вероятность победы

Question

TeamA = {3,6,7,5,3,5,6,2,9,1} 
TeamB = {2,7,0,9,3,6,0,6,2,6}

выводит максимальное количество боев, которое TeamA может выиграть, если они go сражаются оптимальным образом. Считайте, что каждое число в массиве является членом, и этот участник сражается против другого члена другой команды. Например, TeamA [i] будет сражаться с TeamB [i], а TeamA [i] выигрывает, если он больше TeamB. При заданном порядке массива TeamA выиграет только 4 боя один на один. Если мы перегруппируем массив TeamA, есть возможность выиграть 7 fights.ie TeamA==> {3,9,1,5,5,7,2,6,3,6}

Ниже приведен код, который правильно определяет вывод, но из-за сортировки со временем возникают сложности. Пожалуйста, помогите мне оптимизировать код ниже

import java.io.*;
import java.util.*;
public class FightCode{

    // static long[] result ={};
    public static void main(String args[] ) throws Exception {
        Scanner scanner = new Scanner(System.in); 
        try {
            int testCount = scanner.nextInt();

            for (int test=0;test<testCount;test++) {
                int totalMem = scanner.nextInt();     
                Long[] teamA = new Long[totalMem];      
                Long[] teamB = new Long[totalMem]; 
                if (totalMem <1)
                    return;  
                for (int r = 0; r < totalMem; r++) {       
                    teamA[r] = (Long)scanner.nextLong();    
                } 
                for (int i = 0; i < totalMem; i++) {       
                    teamB[i] = (Long)scanner.nextLong();    
                } 
                int count = 0;    

                // int[]swapar = new int[totalMem];  

                Arrays.sort(teamB, Collections.reverseOrder());  
                Arrays.sort(teamA, Collections.reverseOrder()); 
                boolean result = Arrays.equals(teamA, teamB);
                if (result)
                    return;  
                //  System.out.println(Arrays.toString(teamB));
                // System.out.println(Arrays.toString(teamA));   
                for (int a = 0; a < totalMem; a++) {     
                    for (int k=0;k<totalMem;k++) {
                        if(teamA[k] > teamB[a]){
                            // swapar[a] = teamA[k];
                            teamA[k] = 0L;
                            count++;
                            break;
                        } 
                    }  
                } 

                //  System.out.println(Arrays.toString(swapar));
                System.out.println(count);
            }
        } catch(Exception e) {
            System.err.println(e.getStackTrace().toString());
        } finally {
            scanner.close();
        }
    }
}

Answer 1

Я думаю, проблема не в сортировке. Проблема заключается в следующей части

for (int a = 0; a < totalMem; a++) {     
    for (int k=0;k<totalMem;k++) {
        if(teamA[k] > teamB[a]){
            // swapar[a] = teamA[k];
            teamA[k] = 0L;
            count++;
            break;
        } 
    }
}  

Вышеуказанная часть представляет собой сложности сложности TotalMem ^ 2, то есть n в квадрате сложности. Следовательно код получает TLE.

Попробуйте код ниже, это линейная сложность времени и пройдет.

int a = 0, k = 0, count = 0;
while(a < totalMem) {
    if(teamA[a] > teamB[k]) {
        ++count;
        ++k;
    }
    ++a;
}