题解:射击>>枚举–不只是暴力！

算法
CSP2019的前一天，早起到了学校。今天是高三二诊的第一天，恰好CSP和二诊冲掉了，不得已请了假。本来高三是不打算停课的，借此机会重温了一下子机房停课的快乐生活。停一天也是停嘛。
Published

January 31, 2020

CautionContent note — Known errors · 明显错误

射击题解代码片段存在明显笔误和不可编译风险。

  • 双重枚举中 for(int j=1;j<=1;j++) 明显应重新核对。
  • i=1,j=n+k 未声明变量；数组上界 1e6+7 作为浮点字面量也不适合直接做数组大小。
  • 题面是反向回忆生成，不能当作可靠原题描述。

题解 : 射击>>枚举–不只是暴力！

1.前言：

CSP2019的前一天，早起到了学校。今天是高三二诊的第一天，恰好CSP和二诊冲掉了，不得已请了假。本来高三是不打算停课的，借此机会重温了一下子机房停课的快乐生活。停一天也是停嘛。

到了学校发现教练还没到，可能是我太久没有机房停课的生活，忘记了机房的生物钟了。一群人在实验楼连廊里等教练。等到大约八点半教练终于来上班了。（中间还被级部主任误以为是逃考试的学生……

看完了教练发的一套题，感觉挺简单的，做完了还没到中午放学，扭头看旁边同学在干什么，发现我的两个同学(均为高三)在研究一道题。(主角出场

2.题目大意

2.1 ATTATION:

题目过于久远，已经不记得具体是什么了。题目在NOIOJ上面，现在这个网站挂掉了所以题面是我根据之前的代码以及依稀的印象反向编的。

（似乎什么时候听说NOIP会从题库里出原题来着？那我就盲猜一把射击这个题 2020.1.31 …好了，事实证明NOIP取消了，CSP：我和NOIP没有（you）关系

2.2 题面：

一共有N种物品（N<=5e3），你有放回的取4次，每一次可以不取，也可以取 i ，每个物品有权值ai，求四次取到的和比m小的最大值是多少 (0<m<Max_long long,0<ai<MAX_int)

2.3注：

因为m的值非常大，所以没办法背包。

3.题解

首先，这道题是绝世好题。

我记得之前做题的时候见到一道题 P3396 哈希冲突 题解里说这道题是一篇省选论文里的，论文说：根号算法，不只是分块。(这也是一道绝世好题)

那么我也要说，今天的这道题 射击 是：枚举算法，不只是暴力。 这道题第一眼看来没什么思路，首先写搜索，大力剪枝之后最多只能拿到40分 搜索的复杂度是O(n^4)，妥妥的TLE那怎么办呢？ 先上代码：

  #include <iostream>
  #include <cstdio>
  using namespace std;
  long long a[1e6+7],ans;
  template <typename _TP>
  inline void read(_TP &X){
      char ch;int w;X=0;
      while(!isdigit(ch)){w=ch=='-';ch=getchar();}
      while(isdigit(ch)){X=(X<<1)+(X<<3)+(ch^48);ch=getchar();}
      X=w?-X:X;
  }
  int main(){
      int n,m;
      read(n);read(m);
      for(int i=1;i<=n;i++){
          read(a[i]);
      }
      int k=0;
      for(int i=1;i<=n;i++){
          for(int j=1;j<=1;j++){
              ++k;
              a[n+k]=a[i]+a[j];
          }
      }
      sort(a+1,a+n+k+1);
      i=1,j=n+k;
      while(i<=j){
          if(a[i]+a[j]<=m){
              if(a[i]+a[j]>ans)ans=a[i]+a[j];
              ++i;
          }
          else --j;
      }
      cout<<ans;
      return 0;
  }

这就是完整的代码了，什么意思呢？
考虑这样一个问题，我们可以把过程看成两个取两次而不是一个取四次
这里实际上使用了分别枚举的技巧，也就是说，先对前两次进行O(n^2)的枚举 ，记录状态，然后再对后两次取进行O(n^2)的枚举，记录状态。但实际上这两次枚举的结果是一模一样的，所以枚举一次就好了。
最后再对于前两次的结果进行一次O(n^2)的枚举。答案就有了。
这样看起来整体的复杂度是O(n2)的，但是，最后一次枚举的时候实际上状态数量是O(n2)的.其实最后一次的枚举复杂度是O（n^4）的。所以说其实复杂度并没有优化。
枚举的代码是这样的：

    for(int i=1;i<=n;i++){
        for(int j=1;j<=1;j++){
            ++k;
            a[n+k]=a[i]+a[j];
        }
    }

但是
进行了前两次枚举就可以用一种类似贪心的方法进行处理了，也就是

    sort(a+1,a+n+k+1);
        i=1,j=n+k;
        while(i<=j){
            if(a[i]+a[j]<=m){
                if(a[i]+a[j]>ans)ans=a[i]+a[j];
                ++i;
            }
            else --j;
        }

这样，最后一次的贪心是O(n^2)的。