cho hai dãy có cùng n số nguyên dương a1,a2,..an và b1,b2,..bn . shiba muốn tạo ra một dãy cũng có n số nguyên dương c1,c2,c3,..cn thỏa mãn rằng ck(1<=k<=n) là giá trị lớn nhất của a[i]*b[j] với mọi 1<=i<=j<=k . Hay nói một cách khác, shiba cần tạo ra một dãy thỏa mãn rằng ck=max(ai*bj) với mọi (i<=i<=j<=k) Yêu cầu: Bạn hãy giúp shiba tạo và in ra dãy c thỏa mãn điều kiện trên. Input Dòng đầu tiên chứa số nguyên dương n(1<=n<=10^6; . Dòng tiếp theo chứa dãy a1,a2,..an(1<=a[i]<=10^9) , mỗi số cách nhau một khoảng trắng. Dòng cuối cùng chứa dãy b1,b2,b3,..bn(1<=b[i]<=10^9) , mỗi số cách nhau một khoảng trắng. Output Gồm n dòng, dòng thứ i(1<=i<=n) in ra số c[i] thỏa mãn điều kiện (i theo thứ tự tăng dần ). VD: Input: 3 3 2 20 1 4 1 Out put: 3 12 20 để ý điều kiện của n và lưu ý kết quả mảng c có thể rất lớn ( lên đến long long) giải bằng mảng 1 chiều độ phức tạp (On) và dùng thư viện bits/stdc++.h

Code:

#include <bits/stdc++.h>
using namespace std;
long long a[1000001];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  int n;
  long long x,m=0;
  cin>>n;
  for (int i=1;i<=n;i++){
    cin>>x;
    a[i]=max(a[i-1],x);
  }
  for (int i=1;i<=n;i++){
    cin>>x;
    m=max(m,a[i]*x);
    cout<<m<<'\n';
  }
}

Code sẵn.

Ý tưởng:

Do các phần tử của mảng a và b đều là số dương, số lớn nhất tạo được khi ai và bj là lớn nhất.

Giả sử bj cố đinh, số lớn nhất có thể tạo được là max(`a_{1->j}`) * bj.

Thực tế là j có thể < k, tuy nhiên, ta không cần phải tính lại do ta đã tính giá trị bj lớn nhất có thể tạo được với mọi j < k, việc duy nhất ta cần làm là lưu lại bj lớn nhất tính được vào một biến res.

Vậy ta có thể giải quyết bài toán này trong độ phức tạp O(n).

$\\$

Code tham khảo:

#include <bits/stdc++.h>

#define ll long long
#define N 1000005
#define endl "\n"

using namespace std;

template<class T> void readar(T begin, T end) {
    for (T i=begin; i!=end; ++i) cin >> *i;
}

template<class T> void printar(T begin, T end) {
    for (T i=begin; i!=end; ++i) cout << *i << endl;
}

int n, a[N], b[N];

int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    cin >> n;
    readar(a, a+n);
    readar(b, b+n);
    
    ll now=0, res=0;
    for (int i=0; i<n; ++i) {
        now = max(now, (ll)a[i]);
        res = max(res, b[i] * now);
        cout << res << endl;
    }
    
}

$\\$
$\\$
\begin{array}{c|c|c}\color{#ffd710}{\texttt{\{}} \color{#8655d6}{\texttt{\{}}\ \ \color{#8cdcda}{\text{Daoanhviet96}}\ \ \color{#8655d6}{\texttt{\}}} \color{#ffd710}{\texttt{\}}}\end{array}