题意：有多少种方法可以从1,2,3....n中选出3个不同的正整数，使得以他们为三边长可以形成三角形
思路：枚举O(n^3)会超时，设三角形最大的边长x,其他两边分别为y,z。
根据三角形不等式有y+z > x ,所以z的范围是 x-y < z < x
根据这个不等式，当y=1时，显然有不等式是无解的；当y=2的时只有一个解
（z = x-1）.....,当y=x-1时有x-2个解，再排除掉y=z和重复(y1=z2,z1=y2)的情况
y=z 的情况有从x/2+1 到 x-1 的时候会出现，所以会有(x-1)/2个解，减去这个后再除以2就是答案了，而题目要求的是最大的边不超过n的解
#include#include #include #include #include using namespace std; long long f[1000010]; int main(){ f[3] = 0; for (long long x = 4; x <= 1000000; x++) f[x] = f[x-1] + ((x-1)*(x-2)/2 - (x-1)/2) / 2; int n; while (cin >> n){ if (n < 3) break; cout << f[n] << endl; } return 0; }