占坑。。。明天更。。。加油！！
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了一发
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #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);
}
|