论如何补一道南昌网络赛的题补一上午

发表于 | 分类于 | 评论数： | 阅读次数：
论如何补一道南昌网络赛的题补一上午

先上题目

比赛的时候

当时网络赛做这个题的时候，队内又信息交流出问题，让我一直以为是找区间内的最左边的数乘以这个区间的加和算最大值心想dnmd这个怎么可能不用O(N^2)算法?于是果断放弃。。。

周一回来

周一回来重新打开QQ群发现了题解说用单调栈来求解，心想单调栈怎么还能解决这个问题？于是问了问大哥题意是啥后才发现题意都读错了，于是赶紧开始了补题

第一次尝试

首先看到这个题再加上看到单调栈的字眼很容易就想到一个O(3*N)的算法就是O(N)左边扫一遍O(N)右边扫一遍O(N)总共的扫一遍求最大值于是写下了这样的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
long long ans=0,l[500005],r[500005],pre[500005],num[500005];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>num[i];
    pre[i]=pre[i-1]+num[i];
  }
  stack<int> st;
  for(int i=1;i<=n;i++)
  {
    while(st.size()&&num[st.top()]>=num[i])
    st.pop();
    if(st.size())
    l[i]=st.top()+1;
    else
    l[i]=1;
    st.push(i);
  }
  while(st.size())
  st.pop();
  for(int i=n;i;i--)
  {
    while(st.size()&&num[st.top()]>=num[i])
    st.pop();
    if(st.size())
    r[i]=st.top()-1;
    else
    r[i]=n;
    st.push(i);
  }
  for(int i=1;i<=n;i++)
  ans=max(ans,1LL*(pre[r[i]]-pre[l[i]-1])*num[i]);
  cout<<ans;
}

看着也是十分的简洁明了的，但是WA。。。队友说你怕是只能过两个点。。。发现真的就过了两个点。。。然后开始听说有负数要特判，但是我当时还是完全的不明白为啥要特判啊于是索要hack数据。。。队友拿出了:
5
-7 -8 1 -7 -8
这个答案应该是232，留下这一句话开始漏出了笑容，似乎已经预料到我程序要白给了，但是神奇的是我的程序正好出现了232….
这也让我很奇怪，都说这个数据可能会出问题为啥我的没有出问题，虽然我那时候还是觉得不需要负数特判但是我还是自己hack了一波我自己除了一波:
3
0 1 2
结果我的程序出来个4我以为hack成功，还没来得及高兴就发现好像单个2*2就是4哦…于是陷入了僵局提交果然也是wa 2/13
于是乎问了问校外的大佬咋回事啊，大佬很不屑的来了一组:
5
1 -2 -3 -4 -5
我也就试了试出来个65…但是答案显然是70hack成功!!!
我开始分析哪里出了问题发现这个左右边界有可能取的过于大了导致不是区间和最优的情况，对于负数来说区间和尽量的是负数才有可能找到最大的值，于是我开始了第一波修改

第二次尝试

我想着我把前缀后缀求出来然后枚举l-r内的最小前缀后缀不就可以了吗？
于是负数我这样特判: 

1
2
3
4
5
6
7
8
long long minn=INT_MAX;
for(int j=l[i];j<=r[i];j++)
{
  minn=min(minn,pre[r[i]]-pre[j-1]);
  minn=min(minn,post[j]-post[r[i]+1]);
}
minn=min(minn,num[i]);
ans=max(ans,num[i]*minn*1LL);

这个也过了大佬给的hack但是交上去还是wa 2/13…
后来我自己随意hack了一波发现还是不对:
5
1 -2 -3 -2 1
答案显然是21但是我的程序是18…
经过思考发现我这样做不能随意截断导致必须跟着前面的
也就是说如果3-5是最优的那么我肯定会把1-2算上算成1-5是最优的显然这是不对的
我又陷入了沉思…

第三次尝试

实在想不出来问大佬大佬抛了一句看题解，于是我又借鉴了别人的找法，以当前的数为中心枚举左边的前缀和并且枚举右边的前缀和即可这样直接就能保证可以出现了截断式的最优解，问题显得迎刃而解了
通过修改后我的代码为: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
long long ans=-INT_MAX,l[500005],r[500005],pre[500005],num[500005],post[500005];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>num[i];
    pre[i]=pre[i-1]+num[i];
  }
  for(int i=n;i;i--)
  post[i]=post[i+1]+num[i];
  stack<int> st;
  for(int i=1;i<=n;i++)
  {
    while(st.size()&&num[st.top()]>=num[i])
    st.pop();
    if(st.size())
    l[i]=st.top()+1;
    else
    l[i]=1;
    st.push(i);
  }
  while(st.size())
  st.pop();
  for(int i=n;i;i--)
  {
    while(st.size()&&num[st.top()]>=num[i])
    st.pop();
    if(st.size())
    r[i]=st.top()-1;
    else
    r[i]=n;
    st.push(i);
  }
  for(int i=1;i<=n;i++)
  {
    if(num[i]>=0)
    ans=max(ans,1LL*(pre[r[i]]-pre[l[i]-1])*num[i]);
    else
    {
      long long minn1=INT_MAX,minn2=INT_MAX;
      for(int j=l[i];j<=i;j++)
      minn1=min(minn1,pre[i]-pre[j-1]);
      for(int j=i+1;j<=r[i];j++)
      minn2=min(minn2,pre[j]-pre[i]);
      ans=max(ans,num[i]*(minn1+minn2)*1LL);
    }
  }
  cout<<ans;
}

我自己的hack都过了心想可算结束了，但是交上去还是不对。。。wa 12/13….这就相当的神奇了，我这个bug也是想了好久好久问了别人别人也都没有怎么看出来…

第四次尝试

最终我心想算了，直接把别人的手敲一份记他的写法吧可能我的写法哪里有问题，但是敲别人的我也白给一直不对，经过一阵子的debug突然发现第二个for有可能是不走的
也就是说对于这个代码:

1
2
3
4
5
6
long long minn1=INT_MAX,minn2=INT_MAX;
for(int j=l[i];j<=i;j++)
minn1=min(minn1,pre[i]-pre[j-1]);
for(int j=i+1;j<=r[i];j++)
minn2=min(minn2,pre[j]-pre[i]);
ans=max(ans,num[i]*(minn1+minn2)*1LL);

第二个for有可能是不走的！！！于是我赶紧把我自己的代码修改了一下这部分替换成

1
2
3
4
5
6
7
8
9
long long minn1=INT_MAX,minn2=INT_MAX;
for(int j=l[i];j<=i;j++)
minn1=min(minn1,pre[i]-pre[j-1]);
ans=max(ans,num[i]*minn1);
for(int j=i+1;j<=r[i];j++)
{
    minn2=min(minn2,pre[j]-pre[i]);
    ans=max(ans,num[i]*(minn1+minn2)*1LL);
}

交上去可算AC了…..- =

感慨

总的来说还是太嫩了，虽然看着是个模板题但是里面也是暗藏玄机…写着写着我就开始不注意了…代码能力还是很弱,如果说这个题解法的话就是利用单调栈的性质求助以每个数为最小值的可能的最大的边界，这样需要左右各扫一遍然后再线性扫一遍求解，负数特判确实是相当的毒瘤。。。
总体复杂度的话是O(3*N+N^2) N^2部分看起来应该是比较少没有卡掉这个题。。。也算是出的不好吧，但是如果不这么做的话又没有别的思路，至少我是没有别的思路的…
AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
using namespace std;
long long ans=0,l[500005],r[500005],pre[500005],num[500005];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>num[i];
    pre[i]=pre[i-1]+num[i];
  }
  stack<int> st;
  for(int i=1;i<=n;i++)
  {
    while(st.size()&&num[st.top()]>=num[i])
    st.pop();
    if(st.size())
    l[i]=st.top()+1;
    else
    l[i]=1;
    st.push(i);
  }
  while(st.size())
  st.pop();
  for(int i=n;i;i--)
  {
    while(st.size()&&num[st.top()]>=num[i])
    st.pop();
    if(st.size())
    r[i]=st.top()-1;
    else
    r[i]=n;
    st.push(i);
  }
  for(int i=1;i<=n;i++)
  {
    if(num[i]>=0)
    ans=max(ans,1LL*(pre[r[i]]-pre[l[i]-1])*num[i]);
    else
    {
      long long minn1=INT_MAX,minn2=INT_MAX;
      for(int j=l[i];j<=i;j++)
      minn1=min(minn1,pre[i]-pre[j-1]);
      ans=max(ans,num[i]*minn1);
      for(int j=i+1;j<=r[i];j++)
      {
        minn2=min(minn2,pre[j]-pre[i]);
        ans=max(ans,num[i]*(minn1+minn2)*1LL);
      }
    }
  }
  cout<<ans;
}
就算是一分钱，也是对作者极大的支持
------ 本文结束 ------

版权声明

Baccano by baccano is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由baccano创作并维护的Baccano博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。
本文首发于baccano 博客（ http://baccano.fun ），版权所有，侵权必究。

小游戏

---小游戏:要不要来选择一下自己可能的老婆？---

简易发声器

---简易的七键钢琴插件---

可以使用鼠标点击琴键也可以使用主键盘1-7或者小键盘的1-7来操作

那么现在开始吧

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
0%