专栏文章

题解：CF2156E Best Time to Buy and Sell Stock

llinjinkun
CF2156E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min5mpj7
此快照首次捕获于
2025/12/01 20:57
3 个月前
此快照最后确认于
2025/12/01 20:57
3 个月前
查看原文
我真是太菜了……

First

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

Second

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

Detail

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

solution 1

set 的 O(nlog⁡nlog⁡V)O(n \log n \log V) 写法：
CPP
#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(nlog⁡V)O(n \log V)：
CPP
#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 记录。
本人已经累趴，不想动了。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...