题解：P14988 多边形

wrz_pussycat296 · 2026-01-18 18:12:19 · 题解

思路

我来讲一讲此题的暴力做法。

首先，拼成图形的条件是，所有木棍的总和大于最长的木棍的两倍。

我们可以发现，对于每一根作为最长的木棍，一定要让比它短的离它越少越好。

那么，我们可以按木棍长度排序。

然后枚举 k，再枚举最长的木棍，取它下面的 k-1 条木棍进行拼图形，看能不能拼成图形。如果可以，就直接输出。（注意这里进行了剪枝，所以不会超时）。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,a[500005],b[500005],c[500005],o=10001,mod=998244353,ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        b[i]=b[i-1]+a[i];
    }
    for(int i=3;i<=n;i++){
        for(int j=1;j<=n-i+1;j++){
            o=j+i-1;
            if(b[o]-b[j-1]>2*a[o])goto h;
        }
        if(1==2){
            h:;
            cout<<i<<' ';
        }
    }
    return 0;
}