关注
int main()
{
int n, m, x, k;
cin >> n >> m >> x >> k;
vector<int> nums(n, 0);
for (int i = 0; i < n; i++)
cin >> nums[i];
int m_min = 50000;
for (auto its : nums)
m_min = min(its, m_min);
int m_max = m_min + m * k;
int l = 1;
int r = m_max;
while (l < r) {
int mid = (l + r + 1)/2;
vector<int> dp(n, 0);
int numm = 0;
bool b1 = true;
for (int i = 0; i < n; i++) {
int num = 0;
int r0 = i + x < n ? i + x : n-1;
for (int j = i - x>0 ? i - x : 0; j <= r0; j++) {
num += dp[j];
}
if (num * k + nums[i] >= mid) {
continue;
}
else {
int lest = mid - num * k - nums[i];
int num2 = lest / k;
if (lest % k != 0)
num2++;
if (num2 + numm > m) {
b1 = false;
break;
}
dp[r0] += num2;
numm += num2;
}
}
if (b1)
{
l = mid;
}
else
r = mid - 1;
}
cout << (l + r) / 2 << endl;
system("pause");
}
二分查找
查看原帖
6 2
相关推荐
![](https://static.nowcoder.com/fe/file/oss/icon_job.png)
点赞 评论 收藏
分享
06-03 16:21
山东建筑大学 Java 点赞 评论 收藏
分享
牛客热帖
正在热议
# 牛客帮帮团来啦!有问必答 #
1378474次浏览 19121人参与
# 每日一题挑战 #
1655次浏览 142人参与
# 极具前瞻性,现代汽车编程题 #
12589次浏览 232人参与
# 和牛牛一起刷题打卡 #
52157次浏览 4188人参与
# 如何写一份好简历 #
346474次浏览 4821人参与
# 非技术岗薪资爆料 #
57495次浏览 759人参与
# 不去互联网可以去金融科技 #
50066次浏览 515人参与
# 晒一晒我的offer #
4088915次浏览 60897人参与
# 摸鱼打卡站 #
9307次浏览 521人参与
# 提前批简历挂麻了怎么办 #
28196次浏览 523人参与
# 互联网公司评价 #
110328次浏览 1429人参与
# 在国企工作的人,躺平了吗? #
130110次浏览 1898人参与
# 简历中的项目经历要怎么写? #
20292次浏览 301人参与
# 运营人的第一份offer应该如何选 #
42739次浏览 701人参与
# 软件开发薪资爆料 #
907223次浏览 12175人参与
# 产品每日一题 #
3995次浏览 163人参与
# 通信和硬件还有转码的必要吗 #
12537次浏览 109人参与
# 海康威视求职进展汇总 #
131814次浏览 1437人参与
# 来聊聊你目前的求职进展 #
234696次浏览 2969人参与
# 实习学不到东西怎么办? #
41372次浏览 757人参与
# 24届软开秋招面试经验大赏 #
1259442次浏览 18870人参与
# 正在实习的你,有转正机会吗? #
130512次浏览 1242人参与