首页 > 代码库 > Codechef Not a Triangle题解
Codechef Not a Triangle题解
找出一个数组中的三个数,三个数不能组成三角形。
三个数不能组成三角形的条件是:a + b < c
两边和小于第三边。
这个问题属于三个数的组合问题了。暴力法可解,但是时间效率就是O(n*n*n)了,很慢。
不过既然是组合问题就必定可以使用排序后处理的方法降低时间效率的。
这里降低时间效率的方法是:
选一个最大的数c,然后选两个小数a和b,其中a < b,如果符合条件,那么两个数中间的数必定都可以作为b符合条件a + b < c
这样可以把时间效率降到O(n*n)。
这个规律也不好找啊。要非常认真观察,然后总结出来。
处理一个数组,要从小到大,从大到小反复观察,寻找其规律。
原题:http://www.codechef.com/problems/NOTATRI/
#include <stdio.h> #include <stdlib.h> #include <algorithm> using std::sort; class NotATriangle { //细心找出其规律进行优化 int getNotTris_3(int *A, const int n) { sort(A, A+n); int i = 0, j = 1, k = n-1, ans = 0; for ( ; k >= 2; k--) { i = 0, j = k-1; while (i < j) { if (A[i] + A[j] < A[k]) { ans += j - i; i++; } else j--; } } return ans; } public: NotATriangle() { int N = 0; while (scanf("%d", &N) && 0 != N) { int *A = (int *) malloc(sizeof(int)* N); for (int i = 0; i < N; i++) { scanf("%d", &A[i]); } printf("%d\n", getNotTris_3(A, N)); free(A); } } }; int notATriangle() { NotATriangle ntir; return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。