题面
小C是一个可爱的女孩，她特别喜欢世界上最稳定的图形：三角形。有一天她得到了n根木棍，她把这些木棍随意的摆放成一行。小K来和小C玩，他发现了这排木棍，突然想知道在一段区间[l,r]之间的木棍（即第L根到第R根木棍）是否可以组成一个三角形，小C表示她不会，所以请你帮忙。
输入
数据只有一组。
第一行只有一个数字N，代表一共有N根木棍，N<=100000。
第二行为N个数，代表每根木棍的长度。每根木棍的大小不超过1e18。
第三行为一个数字Q，代表询问数目，Q<=100000。
接下来的Q行，每一行有两个数字L和R，代表询问的区间。其中L和R满足1<=L<=R<=N。
输出
对于每个询问，如果可以组成三角形输出”Yes”，否则输出”No”（不需要加引号）。
输如样例
5
2 3 3 4 10
2
1 3
3 5
输出样例
Yes
No
分析题目
首先可以知道斐波那契数列数列第i项等于第i-1和第i-2项之和，可以想到的是当项数大于100时，第100项已经超过1e10了。当搜索的区间长度大于100时，肯定存在这样的三条边构成三角形。为什么？因为斐波那契数列已经是差一点就可以构成三角形了。int 的范围是有限的，在这有限的区间里面最坏情况是斐波那契数列，数量超过这个，一定存在满足构成三角形的三个数。
当个数小于50的时候：
暴力枚举：
当然不是三重循环： 可以枚举最大值。看看是否存在一个三角形包含这条边，最坏的情况是他前面两条边（排好序了）都不能包含，那么这条一定不被其他边包含（简单证明），如果不满足，移除这一条边。那么我们从大到小枚举边的长度即可。
AC代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 1000005
using namespace std
;
int a
[maxn
], b
[maxn
];
int n
, m
;
int judge(int l
, int r
)
{
if(r
-l
+1 >= 100)
return 1;
int pos
= r
- 2;
for(int i
= l
; i
<= r
; i
++)
b
[i
] = a
[i
];
sort(b
+l
,b
+r
+1);
for(int i
= l
; i
<= r
; i
++)
cout
<< b
[i
] << " ";
while(b
[pos
] + b
[pos
+1] <= b
[pos
+2] && pos
> l
) pos
--;
if(pos
== l
- 1) return 0;
if(b
[pos
] + b
[pos
+1] > b
[pos
+2]) return 1;
return 0;
}
int main()
{
scanf("%d",&n
);
for(int i
= 1; i
<= n
; i
++)
scanf("%d",&a
[i
]);
scanf("%d", &m
);
for(int i
= 1;i
<= m
; i
++)
{
int l
, r
;
scanf("%d%d",&l
,&r
);
if(judge(l
,r
))
printf("Yes\n");
else printf("No\n");
}
return 0;
}
本人水平有限，如有任何错误，恳请大家指正，不要误导他人…
题目来源：北航软件学院18级算法分析练习题 错误反馈： 1004183196@qq.com
