显然，若 时无解。
设 分别为 位学生中选择 的人数，由于同学们绝顶聪明，所以易证 。不难发现由定量关系和推出定性关系 。
不难看出题目需要分类讨论后两组赠品是最大还是次大即 种，我们以第一种为例子（假设第一组赠品价值最小、第二组赠品次小、第三组赠品最大）。我们设数组断点为 （），设 中前 个元素的和为 ，容易的出： （ 分别代表第一组、第二组、第三组赠品的价值和）。因为有约束条件 ，所以有 。稍微变形可得 。结合两不等式组得 。我们发现 的取值范围居然是一个可以 求出的区间。当断点 确定时，对于上述的第一种情况，断点 更往左肯定是更优的，即当最小的赠品价值确定时，次小的赠品价值和越小，答案肯定是更优的（由于 ）。
根据上述分析以及结合数据范围，我们可以想到，对于第一种情况，枚举第一个断点 ，并且二分找到符合最左的符合 的 ，并更新答案这样肯定是对的（因为前缀和单调递增所以是可以二分的）。
对于剩下的 种情况也可以用类似的方法求解，时间复杂度为 ，可以通过。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int a[N];
vector<int>p;
int ceildiv2(int A){
return (A>=0)?((A+1)/2):(A/2);
}
int floordiv2(int A){
return (A>=0)?(A/2):((A-1)/2);
}
signed main(){
int n,m,c,k;
cin>>n>>m>>c>>k;
int sum=0;
for(int i=1;i<=n;i++){
cin>>a[i];
}
if(k>3*c){
cout<<"-1\n";
return 0;
}
int t3=min(c,k);
int rem=k-t3;
int t2=min(c,rem);
int t1=k-t3-t2;
p.push_back(0);
for(int i=1;i<=n;i++){
p.push_back(p[i-1]+a[i]);
}
int ans=-1;
//先枚举第一个断点i
//方案1：A<=B<=C
for(int i=0;i<=n;i++){
int L=max(2*p[i],ceildiv2(p[i]+p[n]-m));
int R=min(m+2*p[i],floordiv2(p[i]+p[n]));
if(L>R)continue;
auto it=lower_bound(p.begin()+i,p.end(),L);
if(it!=p.end() && (*it)<=R){
int pj=*it;
int cur=t1*p[i]+t2*(pj-p[i])+t3*(p[n]-pj);
ans=max(ans,cur);
}
}
//方案2：A<=C<=B
for(int i=0;i<=n;i++){
int L=max(ceildiv2(p[n]+p[i]),p[n]-p[i]-m);
int R=min(floordiv2(p[n]+p[i]+m),p[n]-p[i]);
if(L>R)continue;
auto it=upper_bound(p.begin()+i,p.end(),R);
if(it!=p.begin()+i){
it--;
int pj=*it;
if(pj>=L){
int cur=t1*p[i]+t3*(pj-p[i])+t2*(p[n]-pj);
ans=max(ans,cur);
}
}
}
return 0;
}
暂无评论