Znzryb's Blog
0%

ABC-389-E - Square Price（二分答案但不直接查找答案）

Posted on Edited on

思路讲解

Ans(需要最大化)=k1+k2+⋯+knAns(需要最大化)=k_1+k_2+\cdots+k_n

k12∗p1+k22∗p2+⋯+kn2∗pn≤Mk_1^2*p_1+k_2^2*p_2+\cdots+k_n^2*p_n\leq M

购买第 i 种产品的第 j 个花费是

(j2−(j−1)2)∗pi→化简（2j−1）∗pi(j^2-(j-1)^2)*p_i\xrightarrow{化简}（2j-1）*p_i

那不难发现，我们有一个贪心策略，就是优先买便宜的东西，再买贵的东西。

当然，直接这样搞的话，肯定TLE，我们需要找一个价格阈值x，小于x的东西我们买，大于x的东西我们就不买了，最后看总花费是否 ≤ M

https://www.luogu.com.cn/article/imo508fb 然后你会发现WA了两个点，

hack数据：

1
2
3
4
5
6
7
2 25
1 1

应该输出：
7
错误输出：
6

同样起始价格为1，有时要买3个，有时要买4个，那怎么解决？

加了下面的小根堆就万无一失了，因为我们将刚刚超过价格阈值的全部记录下来，再跑一遍看看有没有遗失的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 下面就是把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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#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……）