题目链接
https://vjudge.net/problem/UVA-11401
题意
给定1，2，3，…，n。从这n个数值中选三个不重复的整数作为三角形的三边，求有多少种选法。
分析
设三角形三边由小到大依次是a[i],a[j],a[k].根据任意两边之和大于第三边，我们只要选择的三边满足a[i]+a[j]>a[k]，则一定可以组成三角形。
先通过暴力枚举，看能不能发现什么规律。
当a[i]=1,无解。
当a[i]=2,能选的a[j]和a[k]一定相邻。有（n-1-3+1)*1种,a[j]能选（n-1-3+1）种，对应的a[k]有1种。
当a[i]=3,a[k]比a[j]大的范围在[1,2].有（n-2-4+1)*2+1种，a[j]能选（n-2-4+1）种，对应的a[k]有2种。还多余一个三角形（3，n-1,n).
当a[i]=4,a[k]比a[j]大的范围在[1,3],有（n-3-5+1)*3+2+1种。多余三个三角形（4,n-2,n-1)、(4,n-2,n)、(4,n-1,n)
…
当a[i]=x,a[k]比a[j]大的范围在[1,x-1].有（n-(x-1)-(x+1)+1)*(x-1)+(x-2)+(x-1)+…+2+1.
…
整理后可知，枚举x从2到n-2，累加（n-2x+1)(x-1)+(x-1)(x-2)/2即为所求。
对于（n-2x+1)小于0的情况，我们只累加（x-1)*(x-2)/2.
代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ll;int main()
{ios::sync_with_stdio(false);ll n,k,ans;while(cin>>n && n>=3){k=0;while(k+1<=(n+1)/2) k++;// cout<<"k= "<<k<<endl;ans=0;for(ll i=2;i<=k;i++)ans+=(n-2*i+1)*(i-1)+(i-1)*(i-2)/2;for(ll i=k+1;i<=n-2;i++){ll x=n-i;ans+=x*(x-1)/2;}cout<<ans<<endl;}return 0;
}