题解：AT_abc389_e [ABC389E] Square Price
george0929
·
·
题解
其实这个套路挺经典的。
买一个物品共 k 件需要花 k^2P 元，可以转换为:
已经买了 k-1 件这个物品，再买一件，需要加价 (k^2-(k-1)^2)P=(2\times k-1)P 元。
物品价格以平方速度增长，所以最多购买 $O(\sqrt M)$ 个物品，因此时间复杂度 $O(N\sqrt M)$，使用优先队列优化可以做到 $O((\log N)\sqrt M)$，代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,M;
__int128 m;
__int128 p[200005];
struct node{
int id;
__int128 up,cnt;
bool operator< (const node &b) const{
return up>b.up;
}
};
priority_queue<node> Q;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>M;
m=M;
for(int i=1;i<=n;i++){
int x;cin>>x;
p[i]=x;
Q.push({i,p[i],1});
}
int ans=0;
while(1){
auto u=Q.top();
Q.pop();
if(m<u.up) break;
ans++;
m-=u.up;
u.up=(2*u.cnt+1)*p[u.id];
u.cnt++;
Q.push(u);
}
cout<<ans<<endl;
return 0;
}
```
当然这个复杂度不足以通过此题，我们重新考察这个贪心的过程，每次加价的价格单调不降（即上述代码第 $32$ 行 `u.up` 单调不降），而每次加价会使答案增加 $1$，因此答案随最后一个加价价格的增加而增加。
因此我们考虑二分答案，二分最后一个加价的价格，之后算出每个物品的最大购买件数，检查总费用是否 $\le M$ 即可。
设最后加价价格为 $mx$，则对于物品 $i$，有 $(2\times k-1)P\le mx$，即 $k\le \frac{mx+P}{2P}$。
求出最后加价价格 $mx$ 后，批量处理每个物品购入 $\frac{mx+P}{2P}$ 件。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,p[200005];
bool ck(int mx){
__int128 pri=0;
for(int i=1;i<=n;i++){//p(2*mid-1)<=mx
__int128 t=(mx+p[i])/(2*p[i]);
t*=t;
if(t>(__int128)m) return false;
t*=p[i];
if(t>(__int128)m) return false;
pri+=t;
}
return pri<=m;
}
int getans(int mx){
int ans=0;
for(int i=1;i<=n;i++){//2*mid-1<=mx
ans+=(mx+p[i])/(2*p[i]);
}
return ans;
}
signed 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];
}
int l=1,r=m,res=0;
while(l<=r){
int mid=(l+r)/2;
if(ck(mid)){
res=mid;
l=mid+1;
}else{
r=mid-1;
}
}
cout<<getans(res)<<"\n";
return 0;
}
```
然后你发现你 WA 了两个点，考虑这个例子：
```
2 25
1 1
```
最优解是第一个物品购买 $3$ 个，第二个物品购买 $4$ 个，最后加价价格为 $16-9=7$。
但是如果最后加价价格为 $7$，二分检查时程序会认为每个物品都购买了 $4$ 个，从而返回 `false`。
因此我们得到的最后加价价格上界为 $6$，于是最后批量处理时程序会认为每个物品只能买 $3$ 个，少算了 $1$ 个，然后就 WA 了。
解决方法很简单，少算当且仅当两个物品加价价格一样，因此每个物品最多少算 $1$ 个，答案最多少算 $N$ 个，在批量处理之后，计算出剩余钱数，然后用优先队列处理少算的部分即可。
时间复杂度 $O(N\log M+N\log N)$，可以通过此题。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,p[200005];
bool ck(int mx){
__int128 pri=0;
for(int i=1;i<=n;i++){//检查总费用是否小于等于 M
__int128 t=(mx+p[i])/(2*p[i]);
t*=t;
if(t>(__int128)m) return false;
t*=p[i];
if(t>(__int128)m) return false;
pri+=t;
}
return pri<=(__int128)m;
}
struct node{
int id;
__int128 up,cnt;
bool operator< (const node &b) const{
return up>b.up;
}
};
priority_queue<node> Q;
int getans(int mx){
int ans=0;
for(int i=1;i<=n;i++){//批量处理
int t=(mx+p[i])/(2*p[i]);
ans+=t;
m-=t*t*p[i];
Q.push({i,(__int128)p[i]*(2*t+1),t+1});
}
while(m){//处理少算的部分
auto u=Q.top();
Q.pop();
if(m<u.up) break;
ans++;
m-=u.up;
u.up=(__int128)(2*u.cnt+1)*p[u.id];
u.cnt++;
Q.push(u);
}
return ans;
}
signed 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];
}
int l=1,r=m,res=0;
while(l<=r){//二分最后加价的价格
int mid=(l+r)/2;
if(ck(mid)){
res=mid;
l=mid+1;
}else{
r=mid-1;
}
}
cout<<getans(res)<<"\n";
return 0;
}
```