原题链接：[编程题]山寨金闪闪 这是某节课前同学给我看的题，只不过他的本意在于令人愉♂悦的金闪闪，我的着眼点在于令人愉♂悦的题目。 就结果而言，这道题也确实让我愉♂悦了一整节运筹学课。 题目大意： 给定最多10 ^ 7个长度的数列，指定最多10 ^ 6个区间，判断有多少个区间可以在里面找出构成三角形的三个数。 注意是求满足条件的区间数，而不是求三角形数。 第一想法就是每个区间先排序，挨个判断，但这么做会超时。 于是开始推导： 对于询问区间[L,R]内的所有元素，假设n=R-L+1,把这些元素排序可得非递减序列： x1,x2,x3…xn 如果区间内任意三个元素都无法构成三角形，则根据“两边之和大于等于第三边”可知，这些边满足： x3>=x1+x2 x4>=x2+x3 x5>=x3+x4 … xn>=xn-2+xn-1 取边界情况，即两边之和等于第三边 x3=x1+x2 x4=x2+x3 x5=x3+x4 … xn=xn-2+xn-1 满足以上条件的序列可以表示为： 1a,1a,2a,3a,5a,8a… 此序列即为无法构成三角形的边界序列 因为单个元素的最大值被确定了(int上限为2^31-1,即2147483647)，而该序列又是非递减的，所以令a=1时可以求出最长边界序列的长度 根据前文可得此时边界序列的递推公式： f[1]=f[2]=1 x<=2 f[x]=f[x-1]+f[x-2] x>2 打印可得下表
...... f[43]=433494437 f[44]=701408733 f[45]=1134903170 f[46]=1836311903 f[47]=2971215073 f[48]=4807526976 f[49]=7778742049 f[50]=12586269025观察可知达到第四十七项时已经超过INT上限，即最长边界序列的长度为47 所以我们可以得到该题的算法：
存储所有的n条边长 进行m次查询 查询区间长度大于47，必能满足要求 查询区间小于47，排序，逐个判断具体实现代码：
#include <cstdio> #include <algorithm> using namespace std; const int MAXLEN=1e7+5; int a[MAXLEN]; int b[50]; int main(){ int n,m,answer; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); scanf("%d",&m); answer=0; while(m--){ int l,r; scanf("%d%d",&l,&r); l--; r--; if(r-l+1>47) answer++; else { for(int i=0;i+l<=r;i++) b[i]=a[i+l]; sort(b,b+r-l+1); for(int i=2;i<r-l+1;i++){ if(b[i]<b[i-1]+b[i-2]){ answer++; break; } } } } printf("%d",answer); return 0; }