Anmol_1994 Ответов: 1

Как мне еще больше оптимизировать его для временных ограничений

Как я могу оптимизировать его менее чем за 1 секунду

Что я уже пробовал:

import java.util.*;

class TestClass {

public static void main(String args[] ) {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int a[]=new int[n];
    int b[]=new int[n];
    for(int i=0;i<n;i++)
    {
        a[i]=sc.nextInt();
        b[i]=sc.nextInt();
    }
    long sum=0;
    for(int i=0;i<n-1;i++)
    {
        for(int j=i+1;j<n;j++)
        {
          sum += Math.abs(a[i]-a[j])*(Math.max(b[i],b[j]));   
        }
    }
    System.out.println(sum);
    }

}

Patrice T

Без знания того, что такое этот код, делать особо нечего. код выглядит уже оптимальным.

1 Ответов

Рейтинг:
1

Afzaal Ahmad Zeeshan

Это никогда не будет выполняться менее чем за 1 секунду. Есть много вещей,

1) пользовательский ввод-это запрос, который сам по себе будет больше секунды.
2) размер неизвестен, манипуляция массивом займет много времени.
3) две петли, даже если мы улучшим одну, как насчет второй?
4) функции математической библиотеки также требуют некоторого процессорного времени.

Только одно решение: убедитесь, что размер массивов и циклов меньше 10 элементов. Только тогда это может сработать. Над чем я работал, 

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package hellojava;

/**
 *
 * @author afzaa
 */
public class HelloJava {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int n = 10; 
        int a[] = new int[n];
        int b[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = arr[i];
            b[i] = arr[i];
        }
        long sum=0;
        for(int i=0;i<n-1;i++)
        {
            for(int j=i+1;j<n;j++)
            {
              sum += Math.abs(a[i]-a[j])*(Math.max(b[i],b[j]));   
            }
        }
        System.out.println(sum);
    }
}

Выполнение этой программы занимает ровно 1 секунду. 
run:
1320
BUILD SUCCESSFUL (total time: 1 second)

Видишь? Только то, что я сказал. :)