[SPOJ] NOTATRI – Not a Triangle

原题:http://www.spoj.com/problems/NOTATRI/

---

题目大意:给一个数组, 找到其中不能组成三角形的3-tuple的个数.

---

分析:睡前A一道. 简单的计算. 两边之和<第三边, 先排序一下数组, 然后把第三边取数组最后一个, 也是最大一个数. 然后两个指针left和right, meet in middle, 个数是 right-left, 因为每次当满足条件时, 所有在right和left中的元素, 都可以看成以当前i为第三边和当前的left为一条边时, 移动right往left靠拢,这些可能的组合, 都是满足条件的, 因为right靠谱left是一个递减的过程.

  public void solve(int testNumber, InputReader in, OutputWriter out) {
        int t = in.readInt();
        while (t != 0){
            int[] nums = IOUtils.readIntArray(in,t);
            out.printLine(solve(nums));
            t = in.readInt();
        }

    }
    private int solve(int[] nums){
        int res = 0;
        Arrays.sort(nums);
        for (int i = nums.length - 1; i > 0; i--) {
            int l = 0;
            int r = i-1;
            while (l < r){
                if (nums[l]+nums[r] < nums[i]){
                    res+=(r-l);
                    l++;
                }
                else
                    r--;
            }
        }
        return res;
    }