Znzryb's Blog
0%

Codeforces Round 986 (Div. 2)—C. Alice's Adventures in Cutting Cake

Posted on Edited on

思路排除

这题乍一看好像是二分答案，但仔细一看好像还不太对，毕竟1600，太板了也不太好。

如果这题考二分的话，题面可能是让你求这个v最大可以为多少，这个非常适合二分答案，但显然这题不是这么问的。

我看见以前qq群里有人问什么时候用二分答案（牛客最近一场小白月赛出了道这个），我个人的回答是，你看到一道觉得像的题，都可以想一想能不能用二分答案，然后想一想检查器好不好写？如果检查器复杂度太高（跑一遍就超时），或者检查器所需要的算法可以直接求出该题答案，那么就不太行。

有些时候你也不要对自己要求太高，什么看一眼就知道怎么做。一般来说出现这种情况要么这道题太板了，要么这道题相对于你来说太简单了，我个人认为遇到这种情况大概率这题都不太适合于你平时练习，反而是你要想一想才对于你有提升吧。

思路讲解

搞两个数组存一下，到该位置能有多少个蛋糕（一个从左到右，一个从右到左，以消除左向依赖以及右向依赖）

具体而言是这样的

image

那么，然后如果我们要知道Alice把 [l,r] 这块区域切给自己后，剩下的我怎么知道够不够分那？

L[],R[]现在就开始发挥作用了

剩下区间的蛋糕总数就是L[l-1]+R[r+1]

1
2
3
4
5
6
// 剩下区间的蛋糕总数就是L[l-1]+R[r+1]
inline bool check(int l,int r) {
    if(L[l-1]+R[r+1]<m)
        return false;
    return true;
}

写好 check( ) 剩下的事就简单了，就是用双指针去遍历每种可能的区间，不断更新答案就好了（用的事Acwing的模版）

1
2
3
4
5
6
for(int i=1,j=1;i<=n;++i) {
      while (check(i,j) && j<=n) {
          ans=max(ans,sumA[j]-sumA[i-1]);
          ++j;
      }
  }

AC代码

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
58
59
#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N=static_cast<int>(2e5)+15;
int T,n,m,v,A[N],sumA[N],L[N],R[N];

inline bool check(int l,int r) {
    if(L[l-1]+R[r+1]<m)
        return false;
    return true;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while (T--) {
        cin>>n>>m>>v;
        for(int i=0;i<=n+10;++i)    // 初始化，因为有可能用到超范围部分，所以多初始化一道
            A[i]=0,sumA[i]=0,L[i]=0,R[i]=0;
        for(int i=1;i<=n;++i) {
            cin>>A[i];
            sumA[i]=A[i]+sumA[i-1];
        }
        int curT=0;
        for(int i=1;i<=n;++i) {
            curT+=A[i];
            if(curT>=v)
                curT=0,L[i]=L[i-1]+1;
            else
                L[i]=L[i-1];
        }
        curT=0;
        for(int i=n;i>=1;--i) {
            curT+=A[i];
            if(curT>=v)
                curT=0,R[i]=R[i+1]+1;
            else
                R[i]=R[i+1];
        }
        if(L[n]<m) {
            cout<<-1<<endl;
            continue;
        }
        int ans=0;
        for(int i=1,j=1;i<=n;++i) {
            while (check(i,j) && j<=n) {
                ans=max(ans,sumA[j]-sumA[i-1]);
                ++j;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
// https://codeforces.com/contest/2028/submission/291995395

心路历程（WA，TLE，MLE……）

最早我觉得是二分答案，但接着发现不对。

代码我就不放了，主要原因是这个分蛋糕的Alice不是这m个生物中的一个，如果这题考二分的话，题目可能让你求这个v最大可以为多少。

记得把数组开大点，前面提交out of bound 了

image

然后不要动不动return 0;

&& j≤n 是可以加的，虽然之后的i其实就进入不到这个while里了，但先前的i一定比之后的i更优秀在这种情况下（你想想看，r确定了，l越来越大，[l,r]越来越像，Alice份给自己的就越来越少）

image