专栏文章

题解：P14458 [ICPC 2025 Xi'an R] Let' s Make a Convex!

mmiller2014
P14458题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@min9zo7r
此快照首次捕获于
2025/12/01 22:59
3 个月前
此快照最后确认于
2025/12/01 22:59
3 个月前
查看原文
题目传送门

1.具体思路

1.1 预处理

因为判断若干跟小木棍是否能生成一个凸多边形的式子既有 max⁡\max 也有 ∑\sum，所以我们将 aa 数组排序，并累加和。

1.2 判断

用一个循环，每次判断是否能构成一个非退化的凸多边形。如果不能就将便是选中区间的 ll 与 rr 各减一。

1.3 答案

最终答案就看循环结束后的 ll 和 rr 时候满足条件即可。

2.代码

2.1 预处理

循环加 sort 即可。
CPP
for(int i=1;i<=n;i++)cin>>a[i],s+=a[i],ans[i]=0;
sort(a+1,a+1+n);

2.2 判断

不多做解释。
CPP
while(l&&a[r]*2>=s)s+=a[l--]-a[r--];

2.3 答案

CPP
ans[k]=(a[r]*2<s?1:0)*s;

2.4 ACcode

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,s,l,r,a[200005],ans[200005];
signed main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        l=s=0,r=n;
        for(int i=1;i<=n;i++)cin>>a[i],s+=a[i],ans[i]=0;
        sort(a+1,a+1+n);
        for(int k=n;k;s-=a[++l],k--)
        {
            while(l&&a[r]*2>=s)s+=a[l--]-a[r--];
            ans[k]=(a[r]*2<s?1:0)*s;
        }
        for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
        cout<<"\n";
    }
    return 0;
}

评论

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

正在加载评论...