题解：CF2077D Maximum Polygon

· · 题解

CF2077D Maximum Polygon

这题为啥 3100 啊，我和同学两条区想 1h 直接会了。

考虑一个简单的形式，当固定子序列中出现的最大数为 mx 时，合法的字典序最大的序列怎么求。

有一个贪心是这样的：将序列中大于 mx 的数全部去掉，然后得出一个新的序列 c_1\sim c_m。我们初始判掉无解的情况，然后将所有数选入子序列中，看看怎样操作去增大这个子序列的字典序。

我们可以用单调栈预处理出每个数右边第一个大于它的数的位置。然后我们将序列从左往右扫，对于每一个 i 与右边大于它的位置 p_i，我们尝试去掉 [i,p_i) 中的所有数。这样一来，子序列中的对应项由 c_i 变为 c_{p_i}，字典序增大。

但我们在变换过程中也要维护当前子序列是否合法。由于去掉了很多数，我们还要保证 2mx<sum，因此我们需要判断 i 左边已经加入最终子序列中的数与 p_i 的整个后缀的和 与 2mx 的大小关系是否合法。这个显然可以 O(1) 判断。

感性理解下这个贪心的正确性，我们从前往后地删数，保证使字典序尽量的大。

于是我们可以通过这个贪心 O(n) 求出固定 mx 时的最优子序列。现在考虑不固定 mx 时的方案。

我们考虑从大到小固定 mx，每次 mx 变化时就在区间中删掉大于等于 mx 的元素。对于每个 mx 分别进行一次贪心。这样做的复杂度是 O(n^2) 的，考虑优化。

然后大脑深度思考一下，可以发现这样一个性质：

若以 mx 为最大值无解，则以 x\in (\lfloor \frac {mx}{2}\rfloor,mx) 为最大值时同样无解；若以 mx 为最大值有解，则以 x\in (\lfloor \frac {mx}{2}\rfloor,mx) 为最大值时也有解，但这个解一定没有以 mx 为最大值时的字典序优秀。

感性证明一下，有的地方可能不太严谨：

令 x=k\frac {mx}{2},1\leq k<2，且此时有解，则一定有 2x=k\cdot mx<sum。考虑在当前子序列中加入 mx，则左边为 2mx，右边为 sum+mx，则由于 k>1，因此有 mx<k\cdot mx<sum，可见此时仍然合法。

反过来的证明仍然是类似的，这里不再赘述。

因此，我们从大到小去确定 mx 时，处理完了当前值，便不再需要处理 \frac {mx}{2}\sim mx 之间的值。所以有效的 mx 本质只有 \log V 个，所以我们只需要使用 \log V 次贪心即可完成求解。

那么就做完了，单次贪心复杂度 O(n)，总体复杂度 O(n\log V)，非常可过。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+5;
int t,n,a[N],c[N],len,pl[N],mx,suf[N];
struct number{
    int num,pl;
} b[N];
bool cmp(number x,number y){
    if(x.num==y.num)return x.pl<y.pl;
    return x.num>y.num;
}
bool vis[N];
vector<int> ans,nw;
bool dayu(){
    if(ans.empty())return 1;
    int mi=min(ans.size(),nw.size());
    for(int i = 0;i<mi;++i){
        if(nw[i]>ans[i])return 1;
        else if(nw[i]<ans[i])return 0;
    }
    return ans.size()<nw.size();
}
stack<int> st;
void getxl(){
    len=mx=0;
    for(int i = 1;i<=n;++i){
        if(!vis[i])c[++len]=a[i],mx=max(mx,a[i]); 
    }
    while(!st.empty())st.pop();
    suf[len+1]=0;
    for(int i = len;i;--i)pl[i]=-1,suf[i]=suf[i+1]+c[i];
    for(int i = len;i;--i){
        while(!st.empty() && c[i]>=c[st.top()])st.pop();
        if(!st.empty())pl[i]=st.top();
        st.push(i);
    }
    mx<<=1,nw.clear();
    if(mx>=suf[1])return ;
    int sum=0;
    for(int i = 1;i<=len;++i){
        nw.push_back(c[i]),sum+=c[i];
        if(pl[i]==-1)continue;
        sum-=c[i];
        if(mx<sum+suf[pl[i]]){
            nw.pop_back();
            i=pl[i]-1;
        }else sum+=c[i];
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i = 1;i<=n;++i){
            cin>>a[i];
            b[i]={a[i],i},vis[i]=0;
        }
        sort(b+1,b+n+1,cmp);
        int lim;
        ans.clear();
        for(int lst=1;lst<=n;++lst){
            getxl();
            if(nw.empty()){
                mx=b[lst].num>>1;
                while(b[lst].num>mx&&lst<=n){
                    vis[b[lst].pl]=1,++lst;
                }
                --lst;
                continue;
            }
            if(dayu())ans=nw;
            mx>>=2;
            while(b[lst].num>mx&&lst<=n){
                vis[b[lst].pl]=1,++lst;
            }
            --lst;
        }
        if(ans.empty())cout<<"-1\n";
        else{
            cout<<ans.size()<<'\n';
            for(auto f:ans)cout<<f<<' ';
            cout<<'\n';
        }
    }
    return 0;
}