能量水晶

算法与正确性

将能量从小到大排序。若合成目标能量为b，为了在同样数量下最少花操作，应选不大于b的能量中最大的若干颗。并且可把目标降到所选能量的最大值。因此存在最优解为排序后的连续区间[l,r]，全部增加到a[r]。

维护区间和sum，所需操作为a[r]*(r-l+1)-sum。右端扩展后，若代价超过m，移动左端直至可行，记录最大区间长度。固定右端时，去掉最小元素不会增加代价；右端递增时，之前已不可行的更小左端也不会重新变得可行。因此滑动窗口不会漏解。

时间O(n log n)，空间O(n)。m、能量、区间和及乘法均须64位。数据有负能量、m=0、全部相等以及接近10^18的预算。

难度依据

4 / geekpi-9-v2：排序后确定最优集合为连续段，以64位运算维护递增代价与滑动窗口。

参考程序

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct Fast{static const int Z=1<<20;char b[Z];int p=0,n=0;char get(){if(p==n){n=fread(b,1,Z,stdin);p=0;if(!n)return 0;}return b[p++];}long long read(){char c;do c=get();while(c&&c<=32);bool neg=c=='-';if(neg)c=get();long long x=0;while(c>='0'&&c<='9'){x=x*10+c-'0';c=get();}return neg?-x:x;}}in;
int main(){int n=in.read();long long m=in.read();vector<long long>a(n);for(auto&x:a)x=in.read();sort(a.begin(),a.end());long long sum=0;int l=0,ans=0;for(int r=0;r<n;r++){sum+=a[r];while(a[r]*(r-l+1LL)-sum>m)sum-=a[l++];ans=max(ans,r-l+1);}printf("%d\n",ans);}

本参考解为独立编写的训练参考解，非官方标准程序。测试数据为自建训练数据。