這個問題我一開始沒做出來，參考了https://blog.csdn.net/a1097304791/article/details/87874948#t3?和?https://www.cnblogs.com/albert67/p/10414426.html|
之后才會做，我就權當記錄一下，并且再理一下思路吧：

收獲：1：二分查找在數據量較大的有序數據中的優化作用；

? ? ? ? ? ?2：思維題模摸門道

本題思路：枚舉天數判斷那一天能喝完且最少，可用二分查找優化。

思維上有問題的可能是：咖啡因在一天多次時的損耗-1、-2等不管是先喝咖啡因多得還是咖啡因少的都是一樣的，多的-1和少的-1是一樣的；所以不管你是正序排列還是逆序排列答案都是一樣的；

我加了些注釋：

#include <iostream> #include <cmath> #include <algorithm> using namespace std;typedef long long LL; const int maxn = 210000;int n, m, arr[maxn]; bool cmp(int a, int b) { return a > b; } bool check(int x) { LL sum = 0;for (int i = 1, t = 0; i <= n; i++) {sum += ( arr[i] - t );if (i%x == 0) t++; //這里用得很好, 表示每組為x天if (arr[i] <= t) break; //剪枝：i再增加，arr[i]也不會增加了，可以加速了}/*int k = 1;int t = 0;for (int i = 1; i <= n; ++i){if (k == x)break;if (arr[i] - t <= 0){k++;t = 1;--i;}sum += arr[i] - t;t++;}*/return sum >= m; } int main() {cin >> n >> m;for (int i = 1; i <= n; i++)cin >> arr[i];sort(arr + 1, arr + 1 + n, cmp);int l = 1, r = n + 1, ans = 1 << 30;//有可能完不成/*二分查找的作用在于快速找到最少的可以完成的天數*/while (l < r) {int mid = ( l + r ) / 2;if (check(mid))r = mid, ans = min(ans, mid); //能完成，所以看看能不能天數再少點elsel = mid + 1; //完不成，所以天數加一天}if (ans != 1 << 30) cout << ans << endl;else cout << "-1" << endl;return 0; }

?

總結

以上是生活随笔為你收集整理的Coffee and Coursework的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。