Grand Voting

Dada 举办了一场比赛，但它收到了大量的差评。于是 Dada 决定操控评论。
比赛当前的投票得分为 $s$ ，初始值为 0。
共有 $n$ 个参与者，每个参与者都有一个投票参数 $a_i$ 。
当第 $i$ 个参与者投票时：

如果 $s \ge a_i$ ，他会点赞（upvote），使得 $s$ 增加 1；
如果 $s < a_i$ ，他会点踩（downvote），使得 $s$ 减少 1。
Dada 可以任意调整这些 $n$ 个人的投票顺序。
他想知道：
经过所有人投票后， $s$ 的 最大值 和 最小值 分别是多少？

📥 输入格式

第一行：一个整数 $n$ （ $1 \le n \le 10^5$ ）—— 投票者数量。
第二行： $n$ 个整数 $a_1, a_2, \dots, a_n$ （ $|a_i| \le 10^5$ ）—— 每个投票者的参数。

输出格式

输出两个整数，用空格分隔：

第一个是经过最优投票顺序后可能得到的 最大最终得分；
第二个是可能得到的 最小最终得分。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int mx=0;
    sort(a+1,a+n+1);
    int s=0;
    for(int i=1;i<=n;i++){
        if(a[i]<=s) s++;
        else s--;
    }
    mx=s;
    s=0;
    sort(a+1,a+n+1,greater<int>());
    for(int i=1;i<=n;i++){
        if(a[i]<=s) s++;
        else s--;
    }
    int mn=s;
    cout<<mx<<' '<<mn<<'\n';
    return 0;
}

J. January's Color

L. Let's Make a Convex!

Kevin 有 $n$ 根木棍，第 $i$ 根的长度是 $a_i$ 。
他想从中选出 $k$ 根木棍（ $1 \le k \le n$ ），
使得它们能够组成一个非退化凸多边形（也就是面积不为 $0$ 的多边形）。

Kevin 想要这个多边形的周长尽可能大。
如果对于某个 $k$ 无法组成多边形，则输出 $0$ 。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int a[N],pre[N],M[N],kmin[N];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        kmin[i]=M[i]=0;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i];
    for(int i=1;i<=n;i++){
        int l=1,r=i,ans=i+1;
        while(l<=r){
            int mid=(l+r)>>1;
            if(pre[i]-pre[i-mid]>2*a[i]) r=mid-1,ans=mid;
            else l=mid+1;
        } 
        if(ans<=i) kmin[i]=ans;  
        else kmin[i]=i+1;
    }
    for(int i=1;i<=n;i++)
        if(kmin[i]<=n) M[kmin[i]]=max(M[kmin[i]],i);
    for(int i=1;i<=n;i++) M[i]=max(M[i-1],M[i]);
    for(int i=1;i<=n;i++){
        if(i<=2||M[i]<i) cout<<0<<' ';
        else cout<<pre[M[i]]-pre[M[i]-i]<<' ';
    }
    cout<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

2025 ICPC 亚洲区域赛西安站