北邮ACM2017热身赛-A题

题目

分析

给定一个列数字，求这列数字中的三元组$(a_i,a_j,a_k)$满足下面两个条件

1. $a_i\leq a_j\leq a_k$
2. $a_i+a_j+a_k=0$
   注意：重复的只算一次

思路

先排序

三个元素和为0，那么一定有两个元素大于等于0，一个小于0；或者两个小于等于0，一个大于0。总之不能三个元素都同号

设三个指针，low从前往后扫描，high从后往前扫描，mid在这两个指针中间从前往后扫描：
先固定low指针，从前往后扫描，知道元素值>=0时停止

• 当三个指针指向的元素和为0时，记录下来。
• 当三个指针指向的元素和>0时，high向前移动。
• 当三个指针指向的元素和<0时，mid向后移动。

需要注意的地方：

1. 同一个指针扫过的相等的元素只计算第一次，后面的要略过
2. 元素值的平方已经超过int的最大位数，要用long long型

代码

#include <iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
 
 
int main() {
    int arr[2005] = { 0 };
    char c;
    vector<int> output;
    int samplenum;
    cin >> samplenum;
    while (samplenum)
    {
        long long result = 0;
        int len;
        cin >> len;
        getchar();
        int ii = 0;
        //读入数据
        while ((c = getchar()) != '\n')
        {
            if (c != ' ')//把这句判断条件改动  
            {
                ungetc(c, stdin);
                cin >> arr[ii++];
            }
        }
        //排序
        sort(arr, arr + len);
        //low指针从前向后遍历
        for (int i = 0; i < len; i++) {
            if (i > 0 && arr[i] == arr[i - 1]) {
                continue;
            }
            int lo = i + 1;
            int hi = len - 1;
            while (lo < hi) {
                if ((arr[i] + arr[lo] + arr[hi]) == 0) {
                    long long aa = (long long)arr[i] * arr[i];
                    long long bb = (long long)arr[lo] * arr[lo];
                    long long cc = (long long)arr[hi] * arr[hi];
                    long long aaa = aa + bb + cc;
                    result += aaa;
                    //略过相同元素
                    while (lo + 1 <= hi && arr[lo + 1] == arr[lo]) {
                        lo++;
                    }
                    while (hi - 1 >= lo && arr[hi - 1] == arr[hi]) {
                        hi--;
                    }
                    lo++;
                    hi--;
                }
                else if ((arr[i] + arr[lo] + arr[hi]) > 0) {
                    hi--;
                }
                else {
                    lo++;
                }
            }
        }
        output.push_back(result % 1000000007);
        samplenum--;
    }
     
 
    for (int i = 0; i < output.size(); i++)
    {
        cout << output[i] << endl;
    }   
    //system("pause");
    return 0;
}