分析：这是一道关于能否构成三角形的题目

构成三角形的条件：a+b>c（前提a<=b<=c，也就是排序）再加上a>0&&b>0&&c>0（题目不存在异常数据不考虑）

 所以按照题目要求直接升序排序之后再判断a[i]+a[i+1]>a[i+2]，如果存在直接数量加1

解释一下为什么是a[i]+a[i+1]>a[i+2]就可以判断，有没有情况是a[i]+a[i+1]>a[i+2]不满足但是还存在三角形呢？

升序之后的数组如果存在a[i]+a[i+x]>a[i+y],(x>y>=2),也就是随机取得三个数如果满足三角形的条件

那么一定存在a[i]+a[i+y-1]>a[i+y],(因为是升序的，下标越大数字越大，下标i+y-1>=i+x,所以a[i+y-1]>=a[i+x],等式依然成立)

同理a[i+y-2]>=a[i],所以必定存在a[i+y-2]+a[i+y-1]>a[i+y]，也就是a[i]+a[i+1]>a[i+2]必定存在。。

注意：题目并没有要求求出【l,r】区间有多少三角形所以不要做多余的工作

c++代码如下：

#include
     
      using namespace std;const int MAXN=(int)1e7 + 5;int n,a[MAXN],m;vector
      
       v;int main() {    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)cnt++;//因为区间一旦很大就很容易构成三角形，别人测试出来的边界             else if(r-l+1<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();                bool flag=0;                for(int i=0; i
       
        v[i+2]) {                        flag=1;                        break;                    }                }                if(flag)cnt++;            }        }        printf("%d\n",cnt);    }    return 0;}
       
      
     

举一反三：

现在要求统计数组区间可以构成多少三角形。这是leetcode的一道题目：

c++代码如下：

 

class Solution {
   //题目思想：固定c，左右变量分别再c的左侧滑动public:    int triangleNumber(vector
     
      & nums) {        int count = 0, size = nums.size();        sort(nums.begin(), nums.end());        for (int i = size - 1; i >= 2; i--) {
   //num[i]是c            int left = 0, right = i - 1;//num[left]是a，num[right]是b            while(left < right) {                if (nums[left] + nums[right] > nums[i]) {                    count += (right - left);//应该不用解释吧                    right--;//计算出现在b的所有三角形，b左移                }                else {                    left++;//和太小，a右移                }            }        }        return count;    }};