这是一个关于药品用量的问题。题目给出了医生开了N种药每种药在接下来的ai天里需要服用bi次。需要求出第一天使得这一天及之后的用药总量不超过K。题目要求输出这一天的日期。
可以使用二分查找的方法来解决这个问题。
首先,我们需要定义一个函数check,用来判断给定的日期是否满足条件。在check函数中,我们遍历每种药品,计算从给定日期开始到接下来的a[i]天里需要服用的总次数。如果总次数超过K,则返回false,否则返回true。
接下来,我们使用二分查找来寻找满足条件的第一天。我们将左边界设为1,右边界设为最大的a[i]。每次取中间值mid,然后调用check函数判断mid是否满足条件。如果mid满足条件,则说明第一天在mid之后,将左边界更新为mid+1;如果mid不满足条件,则说明第一天在mid之前,将右边界更新为mid-1。重复以上步骤,直到左边界大于右边界为止。
最后,返回左边界即为第一天的日期。
以下是示例代码实现:
#include <iostream>
#include <vector>
using namespace std;
bool check(int mid, const vector<int>& a, const vector<int>& b, int K) {
int n = a.size();
int total = 0;
for (int i = 0; i < n; i++) {
if (mid > a[i]) {
total += (mid - a[i]) * b[i];
}
}
return total <= K;
}
int findFirstDay(const vector<int>& a, const vector<int>& b, int K) {
int left = 1, right = *max_element(a.begin(), a.end());
while (left <= right) {
int mid = left + (right - left) / 2;
if (check(mid, a, b, K)) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
int main() {
int N, K;
cin >> N >> K;
vector<int> a(N), b(N);
for (int i = 0; i < N; i++) {
cin >> a[i] >> b[i];
}
int firstDay = findFirstDay(a, b, K);
cout << firstDay << endl;
return 0;
}
输入示例:
3 10
1 2
2 3
3 4
输出示例:
2
解释:第一天开始服用药物,到接下来的两天里,每种药物需要的总次数为2+3+4=9,不超过10。所以第一天的日期为2
原文地址: https://www.cveoy.top/t/topic/hSSV 著作权归作者所有。请勿转载和采集!