题解 | #山寨金闪闪#

山寨金闪闪

https://www.nowcoder.com/practice/9363dcb83ca44c61a2c1a8f65aa722b8

解题思路

对于每个客人分配到的区间 $[l,r]$ ，需要判断能否从中选择三个武器组成三角形
关键是利用三角形的性质：任意两边之和大于第三边
优化策略：
- 当区间长度小于3时，无法形成三角形
- 当区间长度大于等于47时，必定能组成三角形（斐波那契数列）
- 其他情况需要排序后判断相邻的三个数是否能组成三角形

代码

cpp
java
python

#include<bits/stdc++.h>
using namespace std;
const int MAXN = (int)1e7 + 5;

int main() {
    int n, a[MAXN], m;
    vector<int> v;
    
    while(~scanf("%d", &n)) {
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        scanf("%d", &m);
        int cnt = 0;
        
        while(m--) {
            int l, r;
            scanf("%d%d", &l, &r);
            if(r-l+1 >= 47)  // 区间长度≥47必定能组成三角形
                cnt++;
            else if(r-l+1 < 3)  // 区间长度<3不可能组成三角形
                continue;
            else {
                v.clear();
                for(int i = l; i <= r; i++)
                    v.push_back(a[i]);
                sort(v.begin(), v.end());
                int len = v.size();
                for(int i = 0; i < len-2; i++) {
                    if(v[i] + v[i+1] > v[i+2]) {
                        cnt++;
                        break;
                    }
                }
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}

import java.util.*;

public class Main {
    static final int MAXN = (int)1e7 + 5;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] a = new int[MAXN];
        ArrayList<Integer> v = new ArrayList<>();
        
        while(sc.hasNext()) {
            int n = sc.nextInt();
            for(int i = 1; i <= n; i++)
                a[i] = sc.nextInt();
            int m = sc.nextInt();
            int cnt = 0;
            
            while(m-- > 0) {
                int l = sc.nextInt();
                int r = sc.nextInt();
                if(r-l+1 >= 47)
                    cnt++;
                else if(r-l+1 < 3)
                    continue;
                else {
                    v.clear();
                    for(int i = l; i <= r; i++)
                        v.add(a[i]);
                    Collections.sort(v);
                    int len = v.size();
                    for(int i = 0; i < len-2; i++) {
                        if(v.get(i) + v.get(i+1) > v.get(i+2)) {
                            cnt++;
                            break;
                        }
                    }
                }
            }
            System.out.println(cnt);
        }
    }
}

import sys

MAXN = 10**7 + 5
a = [0] * MAXN

for line in sys.stdin:
    n = int(line)
    a[1:n+1] = map(int, input().split())
    m = int(input())
    cnt = 0
    
    for _ in range(m):
        l, r = map(int, input().split())
        if r-l+1 >= 47:
            cnt += 1
        elif r-l+1 < 3:
            continue
        else:
            v = sorted(a[l:r+1])
            len_v = len(v)
            for i in range(len_v-2):
                if v[i] + v[i+1] > v[i+2]:
                    cnt += 1
                    break
    
    print(cnt)