給出N條邊，問這些邊能組成多少個不同的三角形，每條邊的長度是不同的。首先我們先

將邊長按照升序排序，然后枚舉兩條短的邊，看最長邊有多少種可能，累加。

#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> using namespace std;const int MAXN = 2012; int T, N; int a[MAXN];int b_s( int len) {int left = 0, right = N - 1;while( left < right) {int mid = ( left + right + 1) >> 1;if( a[mid] >= len)right = mid - 1;elseleft = mid;}return left; }int cal() {int cnt = 0;for( int i = 0; i < N; i ++)for( int j = i + 1; j < N; j ++) {int len = a[j] + a[i];int pos = b_s( len);cnt += (pos - j);}return cnt; }int main() {scanf( "%d", &T);for( int cas = 1; cas <= T; cas ++){scanf( "%d", &N);for( int i = 0; i < N; i ++)scanf( "%d", &a[i]);sort( a, a + N);int ans = cal();printf( "Case %d: %d\n", cas, ans);}return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/Yu2012/archive/2012/04/23/2466107.html

總結(jié)

以上是生活随笔為你收集整理的ACdream OJ 1140 Counting Triangles的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。