ZJNU 1542 - 三角形（续）--中高级

从小到大排序后

先固定一遍，另外两边递增查找

即固定 i，j=i+1，k=j+1

然后让k递增到 a[i]+a[j]<=a[k] 时

此时不能凑成一个三角形

答案增加 k-1-j 组

此时不需要重置 k=j+1

因为 j++ 后 a[j] 会变大

那么在 j~k 之间的所有木棍长度均能再次满足这种 ij 组合

此时只需要把前一个状态的 k 继续往后查找即可

如果 k 查找到了最后，因为i固定，可得 j 不断向后移动，最后能增加的组合有 (n-j)*(n-j-1)/2 组，结束 j 循环，i++

#include<iostream>

#include<algorithm>

using namespace std;

int ar[];

int main()

{

    ios::sync_with_stdio();

    cin.tie();cout.tie();

    int T,n,i,j,k,ans,d;

    cin>>T;

    while(T--)

    {

        cin>>n;

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

            cin>>ar[i];

        sort(ar+,ar+n+);

        ans=;

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

        {

            k=i+;

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

            {

                d=ar[i]+ar[j];

                while(k<=n&&d>ar[k])

                    k++;

                ans+=k--j;

                if(k>n)

                {

                    ans+=(n-j)*(n-j-)/;

                    break;

                }

            }

        }

        cout<<ans<<endl;

    }

    return ;

}

巴特西

ZJNU 1542 - 三角形（续）--中高级

最新文章

热门文章