Z君的妹妹快要过生日了,于是Z君打算种一些花当做生日礼物。但是距离他妹妹的生日只剩下m天了,而花的生长速度太慢了。如果Z君的妹妹看到收到的花太小,她会生气的。于是Z君打算给花浇水来加快花的生长。 已知有n朵花,种在一条直线上,从左到右编号为1,2.....n。Z君每天只能选择位置连续的w朵花来浇水。浇水只在当天有促进生长的效果,且被浇水的花当天会长高1cm(我们可以忽略花自身的生长)。时间紧迫,Z君想在m天后让这n朵花中最矮的花尽量高。 输入 只有一组数据。 第一行为三个整数n m w (1≤w≤n≤105;1≤m≤105) 。 第二行为n个整数a1,a2,...,an(1≤ai≤109) 代表花朵的初始高度。写C++代码
时间: 2024-02-25 18:55:39 浏览: 53
以下是C++代码实现:
```c++
#include <iostream>
#include <deque>
#include <vector>
using namespace std;
int main() {
int n, m, w;
cin >> n >> m >> w;
vector<int> a(n); // 记录花朵高度
for (int i = 0; i < n; i++) {
cin >> a[i];
}
deque<int> q; // 双端队列,存储当前滑动窗口中的花朵下标
for (int i = 0; i < w; i++) {
while (!q.empty() && a[i] < a[q.back()]) {
q.pop_back();
}
q.push_back(i);
}
vector<int> res; // 记录结果
res.push_back(a[q.front()]); // 队列头部对应的下标就是最小值
for (int i = w; i < n; i++) {
if (q.front() <= i - w) { // 队列头部已经超出窗口范围
q.pop_front();
}
while (!q.empty() && a[i] < a[q.back()]) {
q.pop_back();
}
q.push_back(i);
res.push_back(a[q.front()]);
}
int ans = res[m - 1];
for (int i = m; i < res.size(); i++) {
ans = min(ans, res[i]);
}
cout << ans << endl;
return 0;
}
```
阅读全文