51nod-2497-数三角形

占坑。。。明天更。。。加油！！ ps:00:53点交一发 小b有一个仅包含非负整数的数组a，她想知道有多少个三元组(i,j,k)，满足i<j<k且a[i],a[j],a[k]可能作为某个三角形的三条边的边长。

输入 第一行输入一个正整数n，表示数组a中元素个数； 第二行n个非负整数，表示a中元素，以空格隔开； 其中0＜n≤1000，a中任意元素a[i]满足0≤a[i]≤1000。

输出 输出一个数，表示满足题意的三元组个数 输入样例 4 2 2 3 4 输出样例 3 解法：后缀记录一下每个数出现的次数，复杂度n^2，中间因为sum数组开小了wa了一发 代码：

#include<algorithm>
using namespace std;
int p[1010];
int sum[2010];
int a[1010];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    int ans = 0;
    for(int i = n - 1; i >= 0; i--){
        if(a[i] == 0)
            continue;
        for(int j = a[i]; j <=2005; j++)
            sum[j]++;
        for(int j = i - 1; j >= 0; j--){
            if(a[j] == 0)
                continue;
            int l = abs(a[i] - a[j]);
            int r = a[i] + a[j];
            int s = sum[r - 1] - sum[l];
           // printf("%d %d s: %d \n",sum[r-1],sum[l],s);
            if(a[i] > l && a[i] < r)
                s--;
               // printf("%d %d %d\n",l,r,s);
            if(s > 0)
                ans += s;
        }
    }
    printf("%d\n", ans);
}