数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中双调序列插入元素的查询
在这个问题中，我们给定一个双调序列和Q个查询。每个查询包含一个整数x。我们的任务是在每次查询后打印插入整数后的双调序列长度。最后打印双调序列。
问题描述 − 在这里，我们给定一个双调序列。并且有Q个查询，每个查询包含一个要添加到序列中的整数。我们将从每个查询中添加元素到序列中，然后返回双调序列的长度。所有查询完成后，我们将打印双调序列。
双调序列是一种特殊的序列类型，它先递增到一个点（称为双调点），然后递减。
示例 − 1, 5, 6, 8, 9, 7, 5, 2
让我们来看一个例子来更好地理解这个问题：
输入
bseq = {1, 4, 6, 5, 2, 1}
Q = 2
Query = {5, 6 }输出
7 7
{1, 4, 5, 6, 5, 2, 1 }解释
对于第一个查询，要插入的值是5，它可以插入到序列的递增部分，形成序列{1, 4, 5, 6, 5, 2, 1}，长度为7。
对于第一个查询，要插入的值是6，因为6是最大值，所以不能插入。因此，6不会被插入。
最终序列{1, 4, 5, 6, 5, 2, 1}，长度为7。
为了解决这个问题，我们将不得不把双调序列分成两个集合，一个用于序列的递增部分直到最大值。另一个用于序列的递减部分。
现在，对于每个要插入的元素，可能有以下几种情况：
情况1（如果元素大于最大值） − 将元素添加到递增序列的末尾，并更新最大值。
情况2 − 如果元素小于最大值，则首先在递增集合中检查元素是否存在，如果不存在则插入。否则，在递减集合中搜索并添加（如果可能）。
情况3（如果元素等于最大值或该值同时存在于递增和递减集合中） − 则不能添加该元素。
每次查询操作后，我们将通过添加两个集合的长度来找到双调序列的集合，
length(bseq) = length(incSet) + length(decSet)
所有查询完成后，通过打印incSet，然后打印decSet来打印双调序列。
程序说明我们解决方案的工作原理：
示例
#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;
}输出
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
更新于：2020年9月9日
69 次浏览
广告