HDU 4334 Trouble

题目链接：HDU 4334【Trouble】

思路

       哈希+贪心，直接将五个数组分成两个或者三个数组，此时数组相加的时间复杂度为O(n^2)或者O(n3)，然后双重循环数组e和s1并遍历找出s2中是否有满足题意的元素，这个步骤可以使用二分代替还能降低时间复杂度。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#define maxn 2550
using namespace std;
typedef long long ll;
ll a[maxn], b[maxn], c[maxn], d[maxn], e[maxn];

vector<ll> s1, s2, s3;
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    s1.clear(), s2.clear();
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
      scanf("%lld", &a[i]);
    for (int i = 1; i <= n; i++)
      scanf("%lld", &b[i]);
    for (int i = 1; i <= n; i++)
      scanf("%lld", &c[i]);
    for (int i = 1; i <= n; i++)
      scanf("%lld", &d[i]);
    for (int i = 1; i <= n; i++)
      scanf("%lld", &e[i]);

    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        s1.push_back(a[i] + b[j]);
        s2.push_back(c[i] + d[j]);
      }
    }
    sort(s1.begin(), s1.end());

    sort(s2.begin(), s2.end());

    bool vis = true;
    for (int i = 1; i <= n; i++) {
      int p = s2.size() - 1;
      for (int j = 0; j < s1.size() && p >= 0; j++) {
        while (e[i] + s1[j] + s2[p] > 0)
          p--;
        if (e[i] + s1[j] + s2[p] == 0) {
          vis = false;
          cout << "Yes" << endl;
          break;
        }
      }
      if (!vis)
        break;
    }
    if (vis)
      puts("No");
  }
  return 0;
}