【蓝桥备赛】妮妮的月饼工厂—

【蓝桥备赛】妮妮的月饼工厂——二分查找

本文主要是介绍【蓝桥备赛】妮妮的月饼工厂——二分查找，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

妮妮的月饼工厂

个人思路

通过二分查找，寻找满足条件的高度，判定标准是当我们选择mid高度时，我们可以切出的月饼个数是否满足题目要求的 K 个。

	static boolean check(long mid) {if (mid == 0) return false;long res= 0;for (int i = 0; i < n; ++i) {res += arr[i] / mid;}return res >= k;}

当然，此处在二分查找的时候，因为我的左边界是从 0 开始的，且是左闭右闭区间，所以在处理的时候需要判断 0 的情况直接返回 false。

参考代码

Java

import java.io.*;public class Main {static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));static int n;static long k;static long[] arr;static boolean check(long mid) {if (mid == 0) return false;long res= 0;for (int i = 0; i < n; ++i) {res += arr[i] / mid;}return res >= k;}public static void main(String[] args) {Scanner sc = new Scanner();n = sc.nextInt();k = sc.nextLong();arr = new long[n];long l = 0, r = 0;for (int i = 0; i < n; ++i) {arr[i] = sc.nextLong();r= Math.max(arr[i], r);}while (l <= r) {long mid = (r - l) / 2 + l;if (check(mid)) {l = mid + 1;} else {r = mid - 1;}}if (check(r)) {out.println(r);} else {out.println(-1);}out.flush();}
}
// Java 快读
class Scanner {static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));public int nextInt() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return (int) st.nval;}public long nextLong() {try {st.nextToken();} catch (IOException e) {throw new RuntimeException(e);}return (long) st.nval;}
}

C/C++

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 3;
int n;
ll k, arr[N];int check(ll mid)
{if(mid <= 0) return 0;ll cnt = 0;for(int i = 1; i <= n; ++i) cnt += arr[i] / mid;return cnt >= k;
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> k;ll l = 0, r = 0;for(int i = 1; i <= n; ++i) cin >> arr[i], r = max(r, arr[i]);while(l <= r){ll mid = (r - l) / 2 + l;if(check(mid)) l = mid + 1;else r = mid - 1;}if(check(r)) cout << r;else cout << -1;
}