题目描述
解题思路
代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
bool cmp(PII a, PII b)
{
//升序排序
return a.first > b.first;
}
class Solution {
public:
int earliestFullBloom(vector<int>& plantTime, vector<int>& growTime) {
int n = plantTime.size();
vector<PII> rec;
for(int i = 0; i < n; i++)
{
rec.push_back({growTime[i], plantTime[i]});
}
sort(rec.begin(),rec.end(),cmp);
int res = 0, ed = 0;//ed是种植结束的时间,res是最终时间
for(auto item : rec)
{
int gt = item.first, pt = item.second;
ed += pt;
res = max(res, ed + gt);
}
return res;
}
};
关于排序,可以使用一个vector存储下标,然后对下标进行排序,使用lambda自定义排序函数(在cmp里面实现也行,但是两个数组不是全局变量有点麻烦) 十分巧妙!
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
int earliestFullBloom(vector<int>& plantTime, vector<int>& growTime) {
int n = plantTime.size();
vector<int> order(n);
for(int i = 0; i < n; i++)
order[i] = i;
//使用lambda进行排序
//捕获外部作用域中所有变量,并作为引用在函数体中使用(按引用捕获)
sort(order.begin(), order.end(), [&](int i, int j){
return growTime[i] > growTime[j];
});
int ans = 0, ed = 0;
for(int i : order)
{
ed += plantTime[i];
ans = max(ans, ed + growTime[i]);
}
return ans;
}
};