题解：CF2156E Best Time to Buy and Sell Stock

linjinkun · 2025-11-18 17:41:04 · 题解

我真是太菜了……

First

首先看到是博弈，然后很容易想到这道题是个 Ad-hoc。仔细观察，显然答案具有单调性，设亚历克斯要拼命将美化值调到 \ge g，浩要拼命将美化值弄到 <g，假设亚历克斯先走，那么什么情况浩会输？又什么情况浩会赢呢？其实显然，就是设 f_a(g,i) 表示 i 在 a 数组中有多少个 j(1 \le j \le n,j \not= i)，满足 a_{\max(i,j)}-a_{\min(i,j)} \ge g。那么稍微思考即可得出如果 \exists i,f_a(g,i) = 2，这样亚历克斯第一步禁锢了 i 之后，反正 i 有两个匹配 j 和 j'，不管浩删掉哪个亚历克斯都可以选择另一个来使得美化值 \ge g，也就是浩输了，否则的话，那么浩就赢了。

Second

简单推广，发现如果是浩先走（也就是题目所说）其实也没什么区别，容易知道，假设浩第一步选了 p，那么只有 q(1 \le q \le n,q \not=p),a_{\max(p,q)}-a_{\max(p,q)} \ge g 的 q 对应的 f_a(g,q) 会减去 1，那么思路呼之欲出。先枚举 p，然后找到所有的 q，直接判断这些 q 对应的 f_a(g,q) 是不是 \le 2，如果是的话那就没问题，当然你会发现……这样相当麻烦，并且复杂度也没有保证，咋办？显然发现，诶，我们不是只需要判断 f_a(g,i) 是不是 >2 或者 =2 或 =1 或 =0 而已，何必准确？那可能有人问了，那这样找到的 q 就不是全部的了，没法和算出的对浩有威胁的点的数量进行比较，其实……对浩有威胁的点的数量也可以只是不准确的，跟 T4 怎么说呢，有点像，就是那种同时抛弃的感觉，这样可以使正确性没有问题。

Detail

当然了，这里我们 f 显然需要 vector（虽然非人哉出题人让非 vector 的神奇玩意也水过了，话说出题人你太有生活了），然后没必要知道值，直接看前三小记录，然后大小就是值，并且可以同时找出这个点对应哪些点满足，这里顺便维护前三小是 set 比较方便，但是由于 set 有 STL 自带常数并且复杂度不算常数也是单次操作 O(\log n) 的，这样会使复杂度变成 O(n \log n \log V)，不是最优解法。发现维护前三小可以用变量单次 O(1) 维护（只不过稍微有亿点难写，本人调了很久结果初值忘了加 1，我真的很有生活了）。

solution 1

set 的 O(n \log n \log V) 写法：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int a[N];
vector<int>ss[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _;
    cin >> _;
    while(_--)
    {
        int n,maxx = 0;
        cin >> n;
        for(int i = 1;i<=n;++i)
        {
            cin >> a[i];
            maxx = max(maxx,a[i]);
        }
        int l = -maxx,r = maxx,ans = 0;
        while(l<=r)
        {
            int mid = l+r>>1;
            for(int i = 1;i<=n;++i)
            {
                ss[i].clear();
            }
            set<pair<int,int>>s;
            for(int i = 1;i<=n;++i)
            {
                for(auto [x,y]:s)
                {
                    if(a[i]-x>=mid)
                    {
                        ss[i].push_back(y);
                        ss[y].push_back(i);
                    }
                }
                s.insert({a[i],i});
                if(s.size()>3)
                {
                    s.erase(prev(s.end()));
                }
            }
            int w = 0;
            for(int i = 1;i<=n;++i)
            {
                w+=(ss[i].size()>=2);
            }
            int flag = 1;
            for(int i = 1;i<=n;++i)
            {
                int si = ss[i].size();
                int b = (si>=2);
                for(int c:ss[i])
                {
                    b+=(ss[c].size() == 2);
                }
                if(b == w)
                {
                    flag = 0;
                    break;
                }
            }
            if(flag)
            {
                ans = mid;
                l = mid+1;
            }
            else
            {
                r = mid-1;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

AC 记录。

solution 2

变量维护写法，O(n \log V)：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int a[N];
vector<int>ss[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _;
    cin >> _;
    while(_--)
    {
        int n,maxx = 0;
        cin >> n;
        for(int i = 1;i<=n;++i)
        {
            cin >> a[i];
            maxx = max(maxx,a[i]);
        }
        int l = -maxx,r = maxx,ans = 0;
        while(l<=r)
        {
            int mid = l+r>>1;
            for(int i = 1;i<=n;++i)
            {
                ss[i].clear();
            }
            int minn = maxx+1,minnx = 0,cmin = maxx+1,cminn = 0,tmin = maxx+1,tminn = 0;
            for(int i = 1;i<=n;++i)
            {
                if(a[i]-minn>=mid&&minnx)
                {
                    ss[i].push_back(minnx);
                    ss[minnx].push_back(i);
                }
                if(a[i]-cmin>=mid&&cminn)
                {
                    ss[i].push_back(cminn);
                    ss[cminn].push_back(i);
                }
                if(a[i]-tmin>=mid&&tminn)
                {
                    ss[i].push_back(tminn);
                    ss[tminn].push_back(i);
                }
                if(tmin>a[i])
                {
                    tmin = a[i];
                    tminn = i;
                }
                if(cmin>tmin)
                {
                    cmin^=tmin^=cmin^=tmin;
                    cminn^=tminn^=cminn^=tminn;
                }
                if(minn>cmin)
                {
                    minn^=cmin^=minn^=cmin;
                    minnx^=cminn^=minnx^=cminn;
                }
            }
            int w = 0;
            for(int i = 1;i<=n;++i)
            {
                w+=(ss[i].size()>=2);
            }
            int flag = 1;
            for(int i = 1;i<=n;++i)
            {
                int si = ss[i].size();
                int b = (si>=2);
                for(int c:ss[i])
                {
                    b+=(ss[c].size() == 2);
                }
                if(b == w)
                {
                    flag = 0;
                    break;
                }
            }
            if(flag)
            {
                ans = mid;
                l = mid+1;
            }
            else
            {
                r = mid-1;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

AC 记录。

本人已经累趴，不想动了。