Square Price：垃圾卡精度，垃圾卡精度，垃圾卡精度，傻逼出题人，傻逼出题人，傻逼出题人，傻逼出题人，傻逼出题人，傻逼出题人，傻逼出题人。
把 ll 改 __int128 前 WA*22，改 __int128 直接 AC 了，难评。
抛开卡精度这题还是挺好的。
暴力
先考虑暴力思路，显然暴力应该这么打：把所有物品全丢进优先队列里，每次选出价值最小的物品，把多选择一个的物品的价值与当前数量的物品价值做差，丢进优先队列。一直执行直到不能选为止。
显然可以构造全 \(1\) 的数据来把它卡爆，不能过。
正解
考虑优化暴力的过程，不难发现，我们最后取出的结果，代价一定小于等于某一个值。而每个元素选的越多，每一个的代价就越多，因此我们可以二分出最后选出的最大代价，设为 \(mx\)。假设当前在计算第 \(i\) 个元素在此限制下最多能选 \(k\) 个该元素，则可以得到下列不等式：
\[p_i\times(k^2-(k-1)^2)\le mx \]\[p_i\times(2k-1)\times 1 \le mx \]\[2k-1 \le \frac{mx}{p_i} \]\[k \le \frac{mx}{2\times p_i}+\frac{1}{2} \]因此，我们就可以求出 \(k\) 了，之后在 check 时将当前答案加上 \(k^2\times p_i\)，最后看答案是否小于等于 \(m\) 即可。
最后统计答案的时候，因为二分时默认所有选的代价都小于等于 \(mx\)，那么如果 \(mx\) 后面的还有剩余，就还要加上这一部分的答案。
时间复杂度 \(O(n \log V)\)。
注意精度问题，要开 __int128 和 long double，二分边界记得开大！
总结
不论精度问题的话，这题还挺巧妙的。这题能用二分代替优先队列的关键就在于下列几点：
- 是取所有价值中的前 \(x\) 小值，具有单调性。
- 单个元素的贡献能被快速计算。
- 单个元素的代价具有单调性。
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define lc (p<<1)
#define rc ((p<<1)|1)
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi=pair<int,int>;
using pl=pair<ll,pair<ll,pair<ll,ll> > >;
ll n,m,p[200005],res=0;
bool check(ll mx)
{
res=0;
__int128 now=0;
for(int i=1;i<=n;i++)
{
__int128 k=max(__int128(0),__int128(floor(ldb((ldb(1.0*mx)/ldb(p[i])+1.0))/ldb(2.0))));
now+=k*k*p[i];
if(now>m)return 0;
res=res+k;
}
return 1;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>p[i];
ll l=0,r=1e15,mid;
while(l<r)
{
mid=(l+r+1)>>1;
if(check(mid))l=mid;
else r=mid-1;
}
res=0;
__int128 now=0;
for(int i=1;i<=n;i++)
{
ll k=max(__int128(0),__int128(floor(ldb((ldb(1.0*l)/ldb(p[i])+1.0))/ldb(2.0))));
now+=__int128(k)*__int128(k)*__int128(p[i]);
res+=k;
}
for(int i=1;i<=n;i++)
{
__int128 kx=max(__int128(0),__int128(floor(ldb((ldb(1.0*l)/ldb(p[i])+1.0))/ldb(2.0))));
__int128 ky=max(__int128(0),__int128(floor(ldb((ldb(1.0*(l+1))/ldb(p[i])+1.0))/ldb(2.0))));
__int128 cst=__int128(ky)*__int128(ky)*__int128(p[i]),oricst=__int128(kx)*__int128(kx)*__int128(p[i]);
if(kx!=ky&&now-oricst+cst<=m)
{
now=now-oricst+cst;
res++;
}
}
cout<<res;
return 0;
}