0%

【每日一题】华华给月月准备礼物 题解

题目链接

Solution

看完题目就能想到这个题也许可以二分答案。

但是需要知道这个题目的答案可不可以满足单调性。即对于所有$x\in N^{*}$满足条件,则$y\in[1, x)$也满足条件。

很显然这是满足单调性的,如果$x$满足条件,即

$$\sum\limits_{i=1}^{n}\lfloor\frac{a_i}{x}\rfloor \ge k$$

那么对于$y\in[1, x)$而言,显然有

$$\lfloor\frac{a_i}{x}\rfloor\le \lfloor\frac{a_i}{y}\rfloor$$

那么这个题就可以二分答案了。

还有一个点是答案可能会到$\max\limits_{i=1}^{n}a_i$。于是二分范围直接是区间$[1,1000000000]$即可。

本题check的时候可以加一个小小的剪枝。

不过这个题有一点没有说清楚,即使答案不存在的时候要输出$0$,所以当$1$的时候也不满足输出$0$即可。

时间复杂度$O(n\log(\max\limits_{i=1}^{n}a_i))$

Code

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
#include<bits/stdc++.h>
using namespace std;
int a[200005], n, k;
bool chk(int x) {
int ans = 0;
for(int i = 0; i < n; i++) {
ans += a[i] / x;
if(ans >= k) return true; // 及时退出可以加快速度而且防止爆int
}
return false;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> k;
for(int i = 0; i < n; i++) {
cin >> a[i];
}
int left = 1, right = 1000000000, ans = 0;
// 若答案不存在则应该输出0所以此处ans=0
while(left <= right) {
int mid = (left + right) >> 1;
if(chk(mid)) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
cout << ans << '\n';
}

回到开头