牛客网真题-54-山寨金闪闪

本题对于java程序员不友好
开始以为dp能解呢，走不通，就暴力了，超时，然后参考了评论区大佬的C++解法优化了47这个参数,还是不能AC.
其实有这样一种特性，就是1--3是真，那么1--N,N>=3都是真。加了一层hashMap优化，然而只过了36%

import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static int canTriangle(int[] ints){
        if(ints.length < 3){
            return 0;
        }
        int[] ints1 = Arrays.copyOf(ints, ints.length);
        Arrays.sort(ints1);
        for(int i = 0; i < ints1.length - 2; i++){
            if(ints1[i] + ints1[i + 1] > ints1[i + 2]){
                return 1;
            }
        }
        return 0;
    }

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] swords = new int[n];
        for(int i = 0; i < n; i++){
            swords[i] = scanner.nextInt();
        }
        int m = scanner.nextInt();
        HashMap<Integer, Integer> map = new HashMap<>();
        int cnt = 0;
        for(int i = 0; i < m; i++){
            //            cnt += dp[scanner.nextInt() - 1][scanner.nextInt()-1];
            int l = scanner.nextInt() - 1, r = scanner.nextInt() - 1;
            if(l - r + 1 >= 47){
                cnt++;
            }else{
                if(map.containsKey(l) && map.get(l) <= r){
                    cnt++;
                    map.put(l, r);
                }else{
                    if(canTriangle(Arrays.copyOfRange(swords, l, r + 1)) == 1){
                        cnt++;
                        map.put(l, r);
                    }
                }
            }
        }
        System.out.println(cnt);
    }
}