短代码(一个马后炮)

Posted on 无奈复杂

Table of Contents目录

没赶上报名截止日期,一直 not invited。就很难过。

E 的题目描述是这样的。

Description

tz学姐做题很忙,有一些简单的问题需要你帮忙解决:给定三个序列A,B,C和一个整数X, 现在需要找到三个数Ai,Bj,Ck,满足Ai+Bj+Ck = X.

Input

第1行三个整数 L, N, M;

第2行L个整数代表序列A

第3行M个整数代表序列B

第4行N个整数代表序列C

第5行1个整数S代表有S个X。

接下来的S行每行一个整数X

1<=L, N, M<=500, 1<=S<=1000. 所有整数均在32位整数范围内

Output

对于S个询问计算X对应的公式是否能被满足。 如能满足,输出 "YES", 否则输出 "NO"。

Sample Input

3 3 3
1 2 3
1 2 3
1 2 3
3
1
4
10

Sample Output

NO
YES
NO

我当时给出的代码是这样的。

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
  int l,m,n;
  cin>>l>>m>>n;
  int a[l],b[m],c[n];
  for(int&p:a)cin>>p;
  for(int&p:b)cin>>p;
  for(int&p:c)cin>>p;
  sort(c,c+n);
  cin>>n;
  for(int p;cin>>p;){
    for(int q:a)
      for(int r:b)
        if(binary_search(c,c+n,p-q-r)) {
          cout<<"YES\n";
          goto l;
        }
    cout<<"NO\n";
  l:1;
  }
}
//292

由于我不能提交,无法判断它是否超时了。查了一下网上的做法,是把 ab 加起来存到另一个数组里,然后对这个新的数组排序查找。

仔细分析一下就是:

我的方法,排序用了 O(n*log n),查找 O(n**2*log n)

另一个做法,排序 O(n**2*log n),查找 O(n*log n)

看上去好像正好抵消了没什么区别。问题在于查找是多次查找,我们希望每次查找的时间尽量短。

所以改过的代码是这样的:

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
  int l,m,n,r=0;
  cin>>l>>m>>n;
  int a[l],b[m],c[n],S[l*m]; // GNU 扩展的变长数组
  for(int&p:a)cin>>p;
  // range-for 输入第二组数据,同时将输入的数据和第一组的每一个数字相累加,结果存到 `S` 里。
  for(int&p:b) {
    cin>>p;
    for(int&q:a)S[r++]=p+q;
  }
  for(int&p:c)cin>>p;
  sort(S,S+r);
  cin>>n; // 丢弃个数信息,因为不需要
  for(int p;cin>>p;){
    for(int q:c)
      if(binary_search(S,S+r,p-q)){
        puts("YES");
        goto l; // 直接跳到下次输入,不输出 NO
      }
    puts("NO");
  l:1;
  }
}
//311

排名表上最短是345。

但是有什么用呢。我又不能提交(以后一定要提前关注一下)。