随时间变化的代码优化

Question

我需要根据时间复杂度来优化代码。空间复杂性没有问题。我正在寻找更好的逻辑来在最短的时间内解决这个问题。

问题是
输入n和d在每天
正天数-a [n]的份额值的
的利润D-数-b [d]每个利润的值

输出
每d利润显示
1）两个值
或
2）-1

1）二值： - 每一天股票的价值可能会也可能不会发生变化，但如果发生变化，股票的增加变化必须等于利润b [d]。打印索引（从1开始），其中利润与利润完全相同并且索引之间的差异最小。

2）-1，如果不可能

例如

input 
4 2 
1 2 3 5 
3 8 

输出

2 4 
-1 

代码：

#include <cmath> 
#include <cstdio> 
#include <vector> 
#include <iostream> 
#include <algorithm> 
using namespace std; 


int main() { 

    double i,j,k,s=100000000,p,q,flag; 
    double n,d; 
    cin>>n>>d; 
    vector<double> a(n); 
    vector<double> b(d); 
    for(i=0;i<n;++i){ 
     cin>>a[i]; 
    } 
    for(i=0;i<d;++i){ 
     cin>>b[i]; 
    } 
    for(k=0;k<d;++k) 
    { flag=9; 
     p=q=0; 
    for(i=0;i<n-1;++i){ 
      for(j=i+1;j<n;++j){ 
      if((a[j]-a[i])==b[k]){ 
       if(s>(j-i)){ 
        s=j-i; 
        p=i+1; 
        q=j+1; 
        flag=1; 
        break; 
       } 
      } 

     }   
     } 
     s=100000000; 

    if(flag!=9)  
    cout<<p<<" "<<q<<"\n"; 
    else 
    cout<<"-1\n";  
    } 
    return 0; 
} 

Answer 1

您可以存储来代替重新计算为结果，每个好处：

struct Range { 
    std::size_t start; 
    std::size_t last; 
}; 

int duration(const Range& range) 
{ 
    return range.last - range.start;  
} 

bool operator < (const Range& lhs, const Range& rhs) 
{ 
    return duration(lhs) < duration(rhs); 
} 

std::map<int, Range> 
compute_profits(const std::vector<int>& shares){ 
    std::map<int, Range> res; 
    for (std::size_t i = 0; i != shares.size(); ++i) { 
     for (std::size_t j = i + 1; j != shares.size(); ++j) { 
      const auto benefit = shares[j] - shares[i]; 
      const Range range{i, j}; 
      auto p = res.emplace(benefit, range); 

      if (!p.second) { 
       // Already exist, use the better one 
       auto it = p.first; 
       it->second = std::min(it->second, range); 
      } 
     } 
    } 
    return res; 
} 

void show_result(const std::vector<int>& shares, 
       const std::vector<int>& benefits) 
{ 
    auto profits = compute_profits(shares); 

    for (const auto b : benefits) { 
     auto it = profits.find(b); 

     if (it == profits.end()) { 
      std::cout << -1 << std::endl; 
     } else { 
      const auto& range = it->second; 
      std::cout << 1 + range.start << " " << 1 + range.last << std::endl; 
     } 
    } 
} 

Demo

那么复杂#days² + #benefits * log(#profits)

其中#profits是你的解决方案，它是#days² * #benefits

的 #days²

代替