打卡信奥刷题（3624）用C++实现信奥题 P11839 [USACO25FEB] The Best Lineup S-育师

P11839 [USACO25FEB] The Best Lineup S

题目描述

Farmer John 有NNN（1≤N≤2⋅1051 \leq N \leq 2 \cdot 10^51≤N≤2⋅105）头奶牛排成一条队伍aaa。队伍aaa中从前到后第iii头奶牛编号为一个整数aia_iai（1≤ai≤N1 \leq a_i \leq N1≤ai≤N）。可能存在多头奶牛编号为同一整数。

FJ 将以以下方式构造另一条队伍bbb：

初始时，bbb为空。
当aaa非空时，移除aaa最前面的奶牛，并选择是否将该奶牛添加到bbb的最后。

FJ 想要构造队伍bbb，使得bbb中从前到后的编号序列是字典序最大的（见脚注）。

在 FJ 构造队伍bbb之前，他可以执行以下操作至多一次：

选择队伍aaa中的一头奶牛，并将其移动至当前位置之前的任意位置。

假设 FJ 以最优方式执行至多一次上述操作，输出他可以达到的字典序最大的bbb的编号序列。

每个测试点将包含TTT（1≤T≤1001 \leq T \leq 1001≤T≤100）个独立的测试用例。

输入格式

输入的第一行包含TTT。

每一个测试用例的第一行包含NNN。

每一个测试用例的第二行包含NNN个空格分隔的整数a1,a2,…,aNa_1, a_2, \ldots, a_Na1,a2,…,aN。

输入保证所有测试用例的NNN之和不超过10610^6106。

输出格式

对于每一个测试用例输出一行，包含字典序最大的bbb。

输入输出样例 #1

输入 #1

3 5 4 3 2 1 3 6 5 1 2 6 3 4 6 4 1 3 2 1 1

输出 #1

4 3 3 2 1 6 5 4 4 3 2 1 1

说明/提示

样例 1 解释：

在第一个测试用例中，FJ 可以将第五头奶牛移动到第二头奶牛之后。现在，a=[4,3,3,2,1]a = [4, 3, 3, 2, 1]a=[4,3,3,2,1]。可以证明，[4,3,3,2,1][4, 3, 3, 2, 1][4,3,3,2,1]也是字典序最大的bbb。

在第二个测试用例中，FJ 可以将第四头奶牛移动到队伍的最前面。

在第三个测试用例中，FJ 不需要执行任何操作。他可以通过将除第二头奶牛之外的每头奶牛添加到bbb的最后来构造bbb。可以证明，这得到了字典序最大的bbb。

测试点2∼42\sim 42∼4：N≤100N \leq 100N≤100。
测试点5∼85\sim 85∼8：N≤750N \leq 750N≤750。
测试点9∼189\sim 189∼18：没有额外限制。

脚注

我们知道，序列sss的字典序大于序列ttt当且仅当以下条件之一成立：

在si≠tis_i \neq t_isi=ti的第一个位置iii处，有si>tis_i > t_isi>ti。
当不存在这样的iii时，sss的长度大于ttt。

C++实现

#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intT1,n,a[200005];pair<int,int>val[200005];intcmp(pair<int,int>&x,pair<int,int>&y){if(x.first!=y.first)returnx.first>y.first;elsereturnx.second<y.second;}signedmain(){cin>>T1;while(T1--){cin>>n;for(inti=1;i<=n;i++){cin>>a[i];val[i].first=a[i];val[i].second=i;}intma=0,ma2=0,moved=0,outp=0;sort(val+1,val+n+1,cmp);for(inti=1;i<=n;i++){if(val[i].second>ma){ma2=ma;ma=val[i].second;if(outp)cout<<" "<<val[i].first;elsecout<<val[i].first;outp=1;}elseif(val[i].second>ma2&&!moved){ma=val[i].second;if(outp)cout<<" "<<val[i].first;elsecout<<val[i].first;outp=1;moved=1;}}cout<<endl;}return0;}