问题
您将得到大小为n的列表(1-索引),该列表以零初始化。您必须对列表执行m个操作,并输出列表中所有元素的最大值。对于每个操作,给出三个整数a、b和,并且必须将值k添加到从索引到(都包括在内)的所有元素。
Example输入
5 3
1 2 100
2 5 100
3 4 100Expected输出
200解释
第一次更新后的列表将是:
100 100 0 0 0第二次更新后的列表如下:
100 200 100 100 100在第三次更新之后,将:
100 200 200 200 100因此,所需的答案是: 200
First解决方案
我的第一次尝试,我认为是相当可读的(忽略输入和输出的方式处理黑客级别)
#include
#include
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector v(n);
for(int a0 = 0; a0 < m; a0++){
int start, end, val;
cin >> start >> end >> val;
auto it_start = v.begin()+(start-1);
auto it_end = v.begin()+(end);
transform(it_start, it_end , it_start, [k](long long &x){return x+=k;});
}
cout << *max_element(v.begin(),v.end());
return 0;
}Final解决方案
但是,这种方法虽然可读性强,但对于它实际要求的内容来说太慢了,这是它将达到的最大价值。所以我写了这个,它通过了测试,但在我看来更难理解。
#include
#include
#include
int main() {
int n; int m;
std::cin >> n >> m;
using val_type = long long;
std::vector v(n);
while(m--){
val_type start, end, val;
std::cin >> start >> end >> val;
auto it_start = v.begin()+(start-1);
auto it_end = v.begin()+ end;
*it_start += val;
*it_end -= val;
}
val_type max{0};
auto accumulate_max_val = [x=val_type(0),&max](val_type y) mutable{x+=y; if (x>max) max=x;};
std::for_each(v.begin(),v.end(),accumulate_max_val);
std::cout << max;
return 0;
}你会做些什么来改进它?我是适当地使用lambdas和for_each,还是有一种更清晰的方式来表达我想要做的事情?
发布于 2018-01-17 20:48:16
v向量来简化它:正确地将操作a, b, k作为一对操作:将k从a添加到末尾,将k从b+1减到末尾。现在,不再将它们存储在v中,而是将解耦的操作收集到自己的向量中。按索引排序。std::partial_sum,并在结果数组中找到最大值。这将把空间复杂度从\O(N)降到\O( m)\$,并将时间复杂度从\O(n+m)\$改为\O(m\log m)\$。根据约束条件,时间复杂度似乎更好。您还应该记住,对v的访问可能在没有特定顺序的地方到处都是,精心编制的操作序列可能会导致太多的缓存丢失。不过我没有侧写。for_each和lambda)可能会提高可读性。k为负值,则该算法将失败。即使情况并非如此,将max和x初始化为v[0]并在v.begin() + 1启动循环仍然是一个好习惯。https://codereview.stackexchange.com/questions/185320
复制相似问题