Trong bài toán này, chúng ta được cung cấp các truy vấn Chuỗi và Q dạng bitonic. Mỗi truy vấn có một số nguyên x. Nhiệm vụ của chúng ta là in độ dài của chuỗi bitonic sau khi chèn các số nguyên sau mỗi truy vấn. Và ở cuối in chuỗi bitonic.
Mô tả sự cố - Ở đây, chúng ta được cung cấp một chuỗi bitonic. Và có Q truy vấn, mỗi truy vấn chứa một số nguyên sẽ được thêm vào chuỗi. Chúng tôi sẽ thêm các phần tử từ mỗi truy vấn vào chuỗi và sau đó trả về độ dài của chuỗi bitonic. Sau khi hoàn thành tất cả các truy vấn, chúng tôi sẽ in chuỗi bitonic.
Chuỗi biton là một loại chuỗi đặc biệt, tăng tối đa một điểm (được gọi là điểm bitonic), sau đó giảm.
Ví dụ - 1, 5, 6, 8, 9, 7, 5, 2
Hãy lấy một ví dụ để hiểu rõ hơn vấn đề,
Đầu vào
bseq = {1, 4, 6, 5, 2, 1}
Q = 2
Query = {5, 6 } Đầu ra
7 7
{1, 4, 5, 6, 5, 2, 1 } Giải thích
Đối với truy vấn đầu tiên, giá trị sẽ được chèn là 5, giá trị này có thể được chèn vào phần tăng của chuỗi được thực hiện theo trình tự {1, 4, 5, 6, 5, 2, 1}, chiều dài 7.
Đối với truy vấn đầu tiên, giá trị sẽ được chèn là 6, không thể chèn được vì 6 là giá trị tối đa. Vì vậy, 6 sẽ không được chèn.
Chuỗi cuối cùng {1, 4, 5, 6, 5, 2, 1} độ dài 7.
Để giải quyết vấn đề này, chúng ta sẽ phải chia chuỗi bitonic thành hai bộ, một để tăng một phần của chuỗi lên đến giá trị lớn nhất. Cái còn lại cho phần giảm dần của trình tự.
Bây giờ, đối với mọi phần tử được chèn, có thể là các trường hợp sau -
Trường hợp 1 (nếu phần tử lớn hơn giá trị tối đa) - thêm phần tử vào cuối chuỗi ngày càng tăng và cập nhật tối đa.
Trường hợp 2 - nếu phần tử nhỏ hơn giá trị tối đa, hãy kiểm tra tập hợp tăng trước để biết tính khả dụng của phần tử, chèn nếu không có phần tử nào bằng phần tử đó. Nếu không, hãy tìm kiếm trong tập hợp giảm dần và thêm nếu có thể.
Trường hợp 3 (nếu phần tử bằng giá trị tối đa hoặc giá trị có sẵn trong bộ tăng và giảm bot) - không thể thêm phần tử.
Sau mỗi thao tác truy vấn, chúng tôi sẽ tìm thấy tập hợp của chuỗi bitonic bằng cách thêm độ dài của cả hai tập,
length(bseq) = length(incSet) + length(decSet)
Sau khi hoàn tất tất cả các truy vấn, hãy in chuỗi bitonic bằng cách in theincSet và sau đó in decSet.
Chương trình minh họa hoạt động của giải pháp của chúng tôi -
Ví dụ
#include <bits/stdc++.h>
using namespace std;
void calcBitonicSeqLenth(int bSeq[], int n, int query[], int Q){
int maxVal = INT_MIN;
for (int i = 0; i < n; i++)
maxVal = max(maxVal, bSeq[i]);
set <int> incSet, decSet;
incSet.insert(bSeq[0]);
decSet.insert(bSeq[n - 1]);
for (int i = 1; i < n; i++)
if (bSeq[i] > bSeq[i - 1])
incSet.insert(bSeq[i]);
for (int i = n - 2; i >= 0; i--)
if (bSeq[i] > bSeq[i + 1])
decSet.insert(bSeq[i]);
decSet.erase(decSet.find(maxVal));
for (int i = 0; i < Q; i++) {
if (maxVal <= query[i]) {
maxVal = query[i];
incSet.insert(query[i]);
}
else {
if (incSet.find(query[i]) == incSet.end())
incSet.insert(query[i]);
else
decSet.insert(query[i]);
}
int length = incSet.size() + decSet.size();
cout<<"For query "<<(i+1)<<": The length of Bitonic Sequence is "<<length<<endl;
}
cout<<"The Bitonic Sequence at the end of all queries is : ";
set<int>::iterator it;
for (it = incSet.begin(); it != incSet.end(); it++)
cout<<(*it)<<" ";
set<int>::reverse_iterator revIt;
for (revIt = decSet.rbegin(); revIt != decSet.rend(); revIt++)
cout<<(*revIt)<<" ";
}
int main(){
int bSeq[] = { 1, 4, 6, 5, 2, 1 };
int n = sizeof(bSeq) / sizeof(bSeq[0]);
int Q = 2;
int query[] = { 6, 5 };
calcBitonicSeqLenth(bSeq, n, query, Q);
return 0;
} Đầu ra
For query 1: The length of Bitonic Sequence is 6 For query 2: The length of Bitonic Sequence is 7 The Bitonic Sequence at the end of all queries is : 1 4 5 6 5 2 1