TanYz的三角形
发布时间: 2017年12月11日 14:05 最后更新: 2017年12月11日 14:46 时间限制: 1000ms 内存限制: 128M
TanYz在熬夜打CF(伪),发现A题是一个水题,题意为判断3条线段是否能组成1个三角形。
秒掉A题之后,发现B题虽然与A题相似,但是TanYz看得一脸懵逼,完全不会。
想到CF(伪)又要掉分,TanYz感觉这辈子上红名无望,在绝望中打出GG。
不过相信身为dalao的你一定能帮TanYz秒掉这道题,请你帮帮TanYz.
第一行输入一个整数T,表示数据组数。(1 <= T <= 10)
对于每组数据,第一行输入一个整数n,表示线段条数。(1 <= n <= 100000)
第二行输入n个整数ai表示每条线段的长度。(1 <= ai <= 1000)
对于每组数据,输出一行,能构成三角形的方案数。
4 1 2 3 4 4 1 1 1 1
1 4
题意 : 选出3条边,可以构成三角形,问有多少种方案,暴力的话,3个for肯定是超时,其实就是分成3种情况去考虑
1 . 三条边都相等的情况 , 比较简单好想。
2 . 仅有两条边相等的情况,这个也算好想,就是有个坑 要注意下,就是要判断下较短的两条边的和大于第三条边,写的时候忘记了,一直wa !!
3 . 当三条边都不相等的时候,那么3条边一定就有一个顺序,为了确保不重复,可以先枚举一条最小的边,在枚举一条次小边,那么第三条边就可以通过三角形的三边关系来确定,找到第三条变得额范围,要看这个范围有多少个点时,可以通过前缀和来搞定。
代码示例 :
int pre[100005]; int pp[10005]; ll fun(int x){ return 1ll*x*(x-1)*(x-2)/6; } ll fun2(int x, int y){ return 1ll*x*(x-1)/2*y; } int ff(int x){ if (x < 0) return -x; else return x; } int main() { //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); int t, n, x; cin >> t; while(t--){ cin >> n; memset(pre, 0, sizeof(pre)); for(int i = 1; i <= n; i++){ scanf("%d", &x); pre[x]++; } memset(pp, 0, sizeof(pp)); for(int i = 1; i <= 1000; i++){ pp[i] = pre[i]; pp[i] = pp[i] + pp[i-1]; } ll ans = 0; for(int i = 1; i <= 1000; i++){ if (pre[i] >= 3) ans += fun(pre[i]); } //printf("*%lld ", ans); for(int i = 1; i <= 1000; i++){ if (pre[i] >= 2){ for(int j = 1; j <= 1000; j++){ if (j == i) continue; if (pre[j] && i+i > j) ans += fun2(pre[i], pre[j]); } } } //printf("**%lld ", ans); for(int i = 1; i <= 1000; i++){ for(int j = i+1; j <= 1000; j++){ if (pre[i] && pre[j]) { int p = max(ff(i-j+1), j); int u = i + j - 1; if (u > 1000) u = 1000; ans += 1ll*pre[i]*pre[j]*(pp[u] - pp[p]); } } } printf("%lld ", ans); } return 0; }