题解：P12951 [GCJ Farewell Round #2] Collecting Pancakes

· · 题解

闲话

造福一下被要被分类讨论吃掉的后人。

我不明白：这题时限为什么要给到 30 秒。逆天。

切入正题

问题 1

我们先考虑这样一件事：如果两人选择的第一叠煎饼已知的话。Alice 能拿多少煎饼？

举个例子：

注：以上图片建议拖到新窗口打开。下同。

由于每次只能拿到相邻的。所以 Bob 不能跨过 Alice 拿的第一叠煎饼，拿到 Alice 第一叠煎饼左侧的煎饼。

也就是说，Alice 选的第一叠煎饼与端点之间的煎饼，是 Alice 无论何时拿都能拿到的，所以我们可以最后去拿。

Bob 同理。

示意图：

现在唯一存在争议的地方是中间的几叠煎饼。

显然，Alice 和 Bob 一直往中间拿是更优的。

中间两人将会在两个人所选第一叠煎饼之间这个区间的中点相遇。

最终局面如下图。

问题 2

如果只知道 Alice 第一叠选的哪？这时候 Bob 应在哪选第一叠能使得 Alice 拿到的煎饼最少？Alice 最少拿多少？

根据前面的分析，一下策略是最有优的：

第二问则可以将 4 种情况做 4 遍问题 1 之后，将答案取 \min 即可。

做法

枚举 Alice 选哪，之后你就得到了问题 2。

按照问题 2 所写的做即可。

暴力求和为 \operatorname{O}(n^2) 的。可以拿前缀和优化成 \operatorname{O}(n)。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
long long a[N],sum[N];
int la,lb,ra,rb;
int n;
long long ans;
int cnt;
void solve()
{
    cnt++;
    cin>>n;ans=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i]; //前缀和
    cin>>la>>ra>>lb>>rb; 
    for(int i=la;i<=ra;i++) 
    {
        //枚举Alice第一叠煎饼位置
        long long p=0x3f3f3f3f3f3f3f3f; // 选这最少能拿多少煎饼（采取最优策略）
        if(lb<=i-1&&rb>=i-1) p=min(p,sum[n]-sum[i-1]);
        if(lb<=i+1&&rb>=i+1) p=min(p,sum[i]); // 紧贴着
        if(lb>i+1)
        {
            int mid=(lb+i)/2;
            p=min(p,sum[mid]);
        }
        if(rb<i-1)
        {
            int mid=(rb+i-1)/2;
            p=min(p,sum[n]-sum[mid]);           
        } // 选Lb或Rb
        ans=max(ans,p);
    }
    cout<<"Case #"<<cnt<<": "<<ans<<'\n';
}
int T;
signed main()
{
    cin>>T;
    while(T--) solve();
    return 0;
}