题解：P11761 [IAMOI R1] 明码标价

dyc2022 · 2025-02-22 14:52:03 · 题解

更好的阅读体验

考虑一个非常经典的中位数 trick。

二分中位数 mid，将序列中 \le mid 的位置钦定为 -1，>mid 的位置钦定为 1。那么对于一个只包含 \pm 1 的数列，它的中位数为 -1 当且仅当序列之和 \le 0。

这是非常好的，因为我们已经把一个难以刻画的中位数转换成了易于转移的和。

二分出 mid 后，考虑设计 dp_{i,j} 表示在前 i 个数字中任意分段，且每一段的中位数之和 = j 的方案数。转移是简单的，O(n) 的转移都能接受。只需要枚举 i 所属的这一段的第一个位置，对替换成 \pm 1 的序列做一个前缀和即可。

这里选择用一个 std::unordered_map 来存储 dp 数组，复杂度应当是 O(n^3 \log n) 的。

那么这道题就做完了。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 106
using namespace std;
int n,a[N],b[N],sum[N];
unordered_map<int,__int128> dp[N];
int check(int mid)
{
    for(int i=1;i<=n;i++)
        b[i]=(a[i]>mid?1:-1),sum[i]=sum[i-1]+b[i];
    for(int i=0;i<=n;i++)dp[i].clear();
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=-i;j<=i;j++)
            for(int k=1;k<=i;k++)if(sum[i]-sum[k-1]>0)
                dp[i][j]+=dp[k-1][j-1];
            else dp[i][j]+=dp[k-1][j+1];
    __int128 ans=0;
    for(int i=-n;i<=n;i++)
        ans+=(i>0?1:-1)*dp[n][i];
    return ans>0;
}
main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    int l=1,r=2e9,ans;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(check(mid))l=mid+1;
        else ans=mid,r=mid-1;
    }
    printf("%lld\n",ans);
    return 0;
}