Codestorm：Counting Triangles 查各种三角形的个数

题目链接：https://www.hackerrank.com/contests/codestorm/challenges/ilia

这周六玩了一天的Codestorm，这个题目是真的很好玩，无奈只做出了四道题，自己太菜，difficult的题目一道题都没出，把moderate的题目拿出来总结一下吧。

给了一些棍子，每根棍子的长度各不相同，然后问这些棍子组成的锐角三角形的个数、直角三角形的个数、钝角三角形的个数。

思路很明显，枚举前面两根木棒的长度，然后二分第三根木棒的长度。复杂度O(n^2logn)。

代码：

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <string>

#include <cstring>

#pragma warning(disable:4996)

using namespace std;

#define maxn 10005

typedef long long ll;

ll n;

ll val_2[maxn];

ll val[maxn];

ll ha[maxn];

int main()

{

	//freopen("i.txt", "r", stdin);

	//freopen("o.txt", "w", stdout);

	ll i, j, pos, v, v_sum;

	ll cnt1, cnt2, cnt3, pos1, pos2, pos3, pos_sum;

	memset(ha, 0, sizeof(ha));

	scanf("%lld", &n);

	for (i = 1; i <= n; i++)

	{

		scanf("%lld", &val[i]);

		val_2[i] = val[i] * val[i];

		ha[val[i]]++;

	}

	sort(val + 1, val + n + 1);

	sort(val_2 + 1, val_2 + n + 1);

	cnt1 = 0;

	cnt2 = 0;

	cnt3 = 0;

	for (i = 1; i <= n; i++)

	{

		for (j = i + 1; j <= n; j++)

		{

			v = val_2[i] + val_2[j];

			pos = lower_bound(val_2 + j + 1, val_2 + n + 1, v) - val_2;

			if (val_2[pos] == v)

			{

				cnt2 = cnt2 + ha[val[pos]];

				pos3 = pos + ha[val[pos]];

			}

			else

			{

				pos3 = pos;

			}

			pos1 = pos - (j + 1);

			v_sum = val[i] + val[j];

			pos_sum = lower_bound(val + j + 1, val + n + 1, v_sum) - val;

			pos2 = pos_sum - pos3;

			if (pos1 >= 0)

				cnt1 = cnt1 + pos1;

			if (pos2 >= 0)

				cnt3 = cnt3 + pos2;

		}

	}

	cout << cnt1 << " " << cnt2 << " " << cnt3 << endl;

	//system("pause");

	return 0;

}

亮点在后面，题解的思想是，如果对每根棍子按长度排好序之后，用sliding window的思想能够把时间复杂度降到O(n^2)。看了一下这个代码，觉得写得更好，充分利用了前面比较的关系。

代码：

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <string>

#include <cstring>

#pragma warning(disable:4996)

using namespace std;

#define MA(x,y) ((x)>(y)?(x):(y))

const int N = 5002;

int a[N], b[N], n;

int input()

{

    //freopen("i.txt", "r", stdin);

    //freopen("o.txt", "w", stdout);

    scanf("%d", &n);

    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i] * a[i];

    return 0;

}

int sol()

{

    long long x = 0, y = 0, z = 0;

    sort(a + 1, a + n + 1);

    sort(b + 1, b + n + 1);

    for (int i = 1; i <= n; i++)

    {

        int p = i + 1;

        int q = i + 1;

        for (int j = i + 1; j <= n; j++)

        {

            while (p<n && b[i] + b[j] >= b[p + 1])

                p++;

            q = MA(q, p);

            while (q<n && a[i] + a[j]>a[q + 1])

                q++;

            if (b[i] + b[j] == b[p])

            {

                x += MA(p - 1 - j, 0);

                y++;

                z += q - p;

            }

            else

            {

                x += MA(p - j, 0);

                z += q - p;

            }

        }

    }

    cout << x << " " << y << " " << z << endl;

    return 0;

}

int main()

{

    input();

    sol();

    return 0;

}