毕竟是做题经验不足，开始看题被唬住了。题目大意是给定一个数据a[i]，寻找四个数字i, j, k, m, 使得a[m]=a[i]+a[j]+a[k]，并求出max(a[m])。

最容易想到的是暴力算法。求出每个三元组的和，然后再搜索，复杂度为O(n^3)级别的。但是我觉得应该会有更好的解法，就去百度上查。事实上最终我用的也是这种暴力方法。参考别人代码，结合STL。思路大体上是先排序，然后再二分搜索。最后通过的时间是50ms。看了下本题目的status，前面的高人通过时间都是0ms，由此看来本题肯定有优化的可能。只是我不知道罢了。暂且放下。

STL应用太过生疏，仿函数和函数指针的应用还经常混淆。需要加强。

#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

int main(int argc, char *argv[])
{
    int inta[1000], n, wi;

    while ((cin >> n) && n)
    {
        int i, j, m, u;
        wi = 536870912;
        for (i = 0; i < n; ++i)
        {
            cin >> inta[i];
        }

        sort(inta, inta+n);
        
        if (n < 4)
        {
            goto END;
        }

        for (i = n - 1; i >= 0; i--)
            for (m = n - 1; m >= 0; m--)
            {
                if (i == m)
                {
                    continue;
                }
                for (j = m - 1; j > 0; j--)
                {
                    if (j == i)
                    {
                        continue;
                    }

                    u = inta[i] - inta[m] - inta[j];

                    if (u != inta[i] && u != inta[m] && u != inta[j])
                    {
                        if (binary_search(inta, inta+n, u))
                        {
                            wi = inta[i];
                            goto END;
                        }
                    }
                }
            }
      END:
        if (wi == 536870912)
        {
            cout << "no solution" << endl;
        }
        else
            cout << wi << endl;
    }
    
    return 0;
}

• Relative Posts