ABC-389-E - Square Price（二分答案但不直接查找答案） · znzryb
## 思路讲解
$$
Ans(需要最大化)=k_1+k_2+\cdots+k_n
$$
$$
k_1^2*p_1+k_2^2*p_2+\cdots+k_n^2*p_n\leq M
$$
购买第 i 种产品的第 j 个花费是
$$
(j^2-(j-1)^2)*p_i\xrightarrow{化简}（2j-1）*p_i
$$
那不难发现，我们有一个贪心策略，就是优先买便宜的东西，再买贵的东西。
当然，直接这样搞的话，肯定TLE，我们需要找一个价格阈值x，小于x的东西我们买，大于x的东西我们就不买了，最后看总花费是否 ≤ M
[https://www.luogu.com.cn/article/imo508fb](https://www.luogu.com.cn/article/imo508fb) 然后你会发现WA了两个点，
hack数据：
```cpp
2 25
1 1
应该输出：
7
错误输出：
6
```
同样起始价格为1，有时要买3个，有时要买4个，那怎么解决？
加了下面的小根堆就万无一失了，因为我们将刚刚超过价格阈值的全部记录下来，再跑一遍看看有没有遗失的。
```cpp
// 下面就是把check(l)的过程再跑了一遍，只不过加了小根堆
ll cost=0;
for(int i=1;i<=N;++i){
ll j=(l/P[i]+1)/2;
cost+=j*j*P[i];
pq.push((2*(j+1)-1)*P[i]);
}
while (!pq.empty()) {
if(cost+pq.top()>M){
break;
}else{
ans+=1;
cost+=pq.top();
pq.pop();
}
}
cout<<ans<<'\n';
```
## AC代码
AC [https://atcoder.jp/contests/abc389/submissions/61888808](https://atcoder.jp/contests/abc389/submissions/61888808)
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
using namespace std;
typedef unsigned long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10;
ll N,M,P[MAXN],ans;
// 小根堆
priority_queue<ll , vector<ll>, greater<ll>> pq;
inline bool check(ll x){
ll cost=0,res=0;
for(int i=1;i<=N;++i){
ll j=(x/P[i]+1)/2;
if(j==0) // 防除零
continue;
// 防溢出
if(j*P[i] > (M-cost)/j){
return false;
}
cost+=j*j*P[i];
res+=j;
if(cost>M){
return false;
}
}
ans=max(ans,res);
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>N>>M;
for(int i=1;i<=N;++i){
cin>>P[i];
}
sort(&P[1],&P[N+1]);
ll l=0,r=M;
while (l<r) {
ll mid=l+r+1>>1;
if(check(mid)){
l=mid;
}else{
r=mid-1;
}
}
// 下面就是把check(l)的过程再跑了一遍，只不过加了小根堆
ll cost=0;
for(int i=1;i<=N;++i){
ll j=(l/P[i]+1)/2;
cost+=j*j*P[i];
pq.push((2*(j+1)-1)*P[i]);
}
while (!pq.empty()) {
if(cost+pq.top()>M){
break;
}else{
ans+=1;
cost+=pq.top();
pq.pop();
}
}
cout<<ans<<'\n';
return 0;
}
/*
2 25
1 1
AC https://atcoder.jp/contests/abc389/submissions/61888808
*/
```
## 心路历程（WA，TLE，MLE……）