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

miller2014 · 2025-11-11 20:36:04 · 题解

题目传送门

1.具体思路

1.1 预处理

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

1.2 判断

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

1.3 答案

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

2.代码

2.1 预处理

循环加 sort 即可。

for(int i=1;i<=n;i++)cin>>a[i],s+=a[i],ans[i]=0;
sort(a+1,a+1+n);

2.2 判断

不多做解释。

while(l&&a[r]*2>=s)s+=a[l--]-a[r--];

2.3 答案

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

2.4 ACcode

#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;
}