2 条题解
-
0
先从小到大排序。
然后为了最优， 必然是连续的一串数，只要确定 就可以了。
有一个 的暴力就是直接枚举。
考虑进行优化。
假设 。
可以通过 ，得到 。
就可以得到 的范围。
然后确定 。
需要在满足 的情况下尽可能大。
也就是说，对于每个 ，我都可以直接二分找到最优的 。
每个枚举会爆炸。
容易想到除了 取值中最大的之外，其他的 都与 相邻。
因为 ，是否满足只与 有关。
因为如果 不是最大值， 和 不相邻，那么将 的值变大显然可以满足要求。
所以对于最后一个二分，其余的 相邻，所以直接用 st表 上二分找最大的满足条件的位置。
代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=5e5+5; int n,lg[N]; ll a[N],st[N][25],f[N][25],ans; ll ask(int l,int r){//查询最小值 int Lg=lg[r-l]; return min(st[l][Lg],st[r-(1<<Lg)][Lg]); } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%lld",&a[i]); sort(a+1,a+n+1); for(int i=1;i<n;i++)st[i][0]=a[i+1]-a[i],f[i][0]=i+1; for(int p=1;p<=20;p++){ for(int i=1;i<n;i++)st[i][p]=min(st[i][p-1],st[f[i][p-1]][p-1]),f[i][p]=f[f[i][p-1]][p-1]; } for(int i=1;i<=n;i++)lg[i]=lg[i>>1]+1; for(int i=5;i<=n-2;i++){ ll S=0; for(int j=i-1;j>=i-4;j--)S+=a[j]; int a2=lower_bound(a+1,a+n+1,S-a[i])-a-1;//二分找到a2可行区间的最大值 if(a2<=i)continue; int a1=lower_bound(a+1,a+n+1,a[i]+a[a2])-a-1;//再二分一下a1的最大值 if(a1<=a2){ int l=i+1,r=a2-1,ccf=0; if(ask(l,r)>=a[i]||l>r)continue; while(l+1<r){//二分，找到满足条件最大的位置 int mid=l+r>>1; if(ask(mid,a2-1)<a[i])l=mid; else r=mid; } if(ask(r,a2-1)<a[i])ccf=r; else ccf=l; ans=max(ans,S+a[i]+a[ccf]+a[ccf+1]); } else ans=max(ans,S+a[i]+a[a1]+a[a2]); } if(ans==0)puts("-1"); else printf("%lld",ans); return 0; } -
0
houzhiyuan LV 6 @ 2021-11-19 9:46:55
有另外一种更加简单的做法。
还是 的结论，有 的暴力。
考虑如果不合法，那么排序后每相邻的 个数都不合法，一定会有 相当于 个就把规模缩小了一半。
所以 个数一定有解。
排序后选最大的 个数，暴力就好了。
代码
#include<bits/stdc++.h> #define int long long using namespace std; const int N=500005; int n,a[N],ans,sum[N]; signed main(){ scanf("%lld",&n); for (int i=1;i<=n;++i)scanf("%lld",&a[i]); sort(a+1,a+n+1,greater<int>()); int ans=-1,logN=210; for (int i=1;i<=logN;++i) for (int j=i+1;j<=min(logN,n-5);++j) for (int k=j+1;k<=min(logN,n-4);++k) if ((a[i]<a[j]+a[k]) && (a[k+1]+a[k+2]+a[k+3]+a[k+4]>a[j]+a[k])) ans=max(ans,a[i]+a[j]+a[k]+a[k+1]+a[k+2]+a[k+3]+a[k+4]); printf("%lld\n",ans); return 0; }
- 1
信息
- ID
- 43
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者
-