企业官网建设流程全解析

题目描述

题目要求从按到达顺序排列的导弹高度序列中，找出最长严格递增子序列（LIS，Longest Increasing Subsequence\texttt{LIS，Longest Increasing Subsequence}LIS，Longest Increasing Subsequence），并输出子序列的长度和该子序列本身。题目保证解唯一。

输入格式

第一行一个整数TTT，表示测试用例的数量，后面跟一个空行。每个测试用例包含若干行，每行一个整数（导弹高度），以空行结束。两个连续测试用例之间由一个空行分隔。

输出格式

对于每个测试用例，输出一行Max hits: X，其中XXX为最长子序列的长度，然后输出该子序列中的每个高度（每行一个）。两个连续测试用例的输出之间由一个空行分隔。

样例

输入

1 1 6 2 3 5

输出

Max hits: 4 1 2 3 5

题目分析

本题的核心是求解最长严格递增子序列，并输出子序列本身。由于题目保证解唯一，可以直接使用经典的O(nlog⁡n)O(n \log n)O(nlogn)贪心加二分算法，并记录前驱信息。

算法

• 使用数组mmm记录每个长度的最小末尾值。
• 使用数组indexer\textit{indexer}indexer记录每个长度对应的末尾元素在原序列中的索引。
• 使用数组parent\textit{parent}parent记录每个元素在其最长子序列中的前驱索引。
• 遍历每个元素xxx：
  • 若xxx大于mmm的最后一个元素，则追加到mmm末尾，记录前驱。
  • 否则，在mmm中找到第一个大于等于xxx的位置，替换为xxx，并更新前驱信息。
• 最终，indexer\textit{indexer}indexer的最后一个元素即为最长子序列最后一个元素的索引，通过parent\textit{parent}parent回溯得到整个子序列。

复杂度分析

时间复杂度O(nlog⁡n)O(n \log n)O(nlogn)，空间复杂度O(n)O(n)O(n)。

代码实现

// Strategic Defense Initiative// UVa ID: 497// Verdict: Accepted// Submission Date: 2016-07-16// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;vector<int>numbers,parent,indexer;intlis(){parent.clear();indexer.clear();parent.resize(numbers.size());vector<int>m;m.push_back(numbers.front());indexer.push_back(0);parent[0]=-1;for(inti=1;i<numbers.size();i++){if(numbers[i]>m.back()){m.push_back(numbers[i]);parent[i]=indexer.back();indexer.push_back(i);}else{intn=lower_bound(m.begin(),m.end(),numbers[i])-m.begin();m[n]=numbers[i];if(n==0)parent[i]=-1;elseparent[i]=indexer[n-1];indexer[n]=i;}}returnm.size();}voidfindPath(inti){if(parent[i]!=-1)findPath(parent[i]);cout<<numbers[i]<<'\n';}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;getline(cin,line);intcases=stoi(line);getline(cin,line);for(inti=1;i<=cases;i++){if(i>1)cout<<endl;numbers.clear();while(getline(cin,line),line.length()>0)numbers.push_back(stoi(line));cout<<"Max hits: "<<lis()<<'\n';findPath(indexer.back());}return0;}