Two integer sequences existed initially — one of them was?strictly?increasing, and the other one —?strictly?decreasing.
Strictly increasing sequence is a sequence of integers?[x1<x2<?<xk][x1y2>?>yl]. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.
They were merged into one sequence?aa. After that sequence?aa?got shuffled. For example, some of the possible resulting sequences?aa?for an increasing sequence?[1,3,4][1,3,4]and a decreasing sequence?[10,4,2][10,4,2]?are sequences?[1,2,3,4,4,10][1,2,3,4,4,10]?or?[4,2,1,10,4,3][4,2,1,10,4,3].
This shuffled sequence?aa?is given in the input.
Your task is to find?any?two suitable initial sequences. One of them should be?strictly?increasing and the other one —?strictly?decreasing. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.
If there is a contradiction in the input and it is impossible to split the given sequence?aa?to increasing and decreasing sequences, print "NO".
Input
The first line of the input contains one integer?nn?(1≤n≤2?1051≤n≤2?105) — the number of elements in?aa.
The second line of the input contains?nn?integers?a1,a2,…,ana1,a2,…,an?(0≤ai≤2?1050≤ai≤2?105), where?aiai?is the?ii-th element of?aa.
Output
If there is a contradiction in the input and it is impossible to split the given sequence?aa?to increasing and decreasing sequences, print "NO" in the first line.
Otherwise print "YES" in the first line and?any?two suitable sequences. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.
In the second line print?nini?— the number of elements in the?strictly increasingsequence.?nini?can be zero, in this case the increasing sequence is empty.
In the third line print?nini?integers?inc1,inc2,…,incniinc1,inc2,…,incni?in the?increasing?order of its values (inc1<inc2<?<incniinc1
In the fourth line print?ndnd?— the number of elements in the?strictly decreasingsequence.?ndnd?can be zero, in this case the decreasing sequence is empty.
In the fifth line print?ndnd?integers?dec1,dec2,…,decnddec1,dec2,…,decnd?in the?decreasing?order of its values (dec1>dec2>?>decnddec1>dec2>?>decnd) — the?strictly decreasing?sequence itself. You can keep this line empty if?nd=0nd=0?(or just print the empty line).
ni+ndni+nd?should be equal to?nn?and the union of printed sequences should be a permutation of the given sequence (in case of "YES" answer).
您將得到一個(gè)由nn整數(shù)組成的數(shù)組aa讯榕。您可以執(zhí)行以下操作任意次數(shù)（可能為零）：選擇一對(duì)指數(shù)（i骤素，j）（i，j）愚屁，使i?j=1 i?j=1（指數(shù)i i和j j相鄰）济竹，并設(shè)置a i：=a i+a i?a j a i：=a i+a i?a j選擇一對(duì)指數(shù)（i，j）（i霎槐，j）送浊，使i?j=1 i?j=1（指數(shù)i i和j j相鄰），并設(shè)置a i：=a i?a i?a j a i：=a i?a i?a j丘跌。數(shù)值x x表示x x的絕對(duì)值袭景。例如唁桩，4=4 4=4，?3=3?3=3浴讯。您的任務(wù)是找到獲取相等元素?cái)?shù)組所需的最小操作數(shù)朵夏，并打印操作順序。它保證您總是可以使用這些操作獲得相等元素的數(shù)組榆纽。注意仰猖，每次操作后，當(dāng)前數(shù)組的每個(gè)元素的絕對(duì)值不應(yīng)超過(guò)10181018奈籽。輸入輸入的第一行包含一個(gè)整數(shù)n n（1≤n≤2 1051≤n≤2 105）——aa中的元素?cái)?shù)饥侵。輸入的第二行包含nn整數(shù)a1，a2衣屏，…躏升，an a1，a2狼忱，…膨疏，an（0≤ai≤2 1050≤ai≤2 105），其中ai ai是aa的第二個(gè)元素钻弄。產(chǎn)量在第一行中佃却，打印一個(gè)整數(shù)kk——獲得相等元素?cái)?shù)組所需的最小操作數(shù)。在下一個(gè)KK行中窘俺，打印操作本身饲帅。pp th操作應(yīng)打印為整數(shù)的三倍（tp，ip瘤泪，jp）（tp灶泵，ip，jp）对途，其中tp tp是11或22（11表示執(zhí)行第一種類型的操作赦邻，22表示執(zhí)行第二種類型的操作），ip ip和jjp是數(shù)組相鄰元素的索引实檀，這樣1≤ip惶洲，jp≤n1≤ip，jp≤n劲妙，ip?jp|=1 ip?jp=1.請(qǐng)參閱示例以獲得更好的理解。注意儒喊，每次操作后镣奋，當(dāng)前數(shù)組的每個(gè)元素的絕對(duì)值不應(yīng)超過(guò)10181018。如果有許多可能的答案怀愧，您可以打印任何答案侨颈。
大意就是給你一個(gè)數(shù)組余赢，問(wèn)能否讓每個(gè)元素進(jìn)入遞增或遞減序列，最后形成一個(gè)嚴(yán)格遞減和遞增的序列哈垢。
我的理解：
就是給一個(gè)序列妻柒，如有三次重復(fù)數(shù)字，則輸出No
如不重復(fù)耘分，則要分成遞增举塔，遞減數(shù)組，然后原序列中如果沒(méi)有重復(fù)（只重復(fù)兩次）就全給遞減序列求泰，如果有重復(fù)央渣，重復(fù)的遞增給遞增序列。
網(wǎng)上找的并理解的代碼
#include<stdio.h>#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
int a[200005];//用來(lái)存合成序列
int b[200005];//用來(lái)存遞增序列
int c[200005];//用來(lái)存遞減序列
int main(){
int n;
int i;
while(scanf("%d",&n)!=EOF){
int count1=0;//用來(lái)存遞減序列的個(gè)數(shù)
int count2=0;//用來(lái)存遞增序列的個(gè)數(shù)
int flag=0;//用來(lái)判斷數(shù)組中是否有三個(gè)相同的數(shù)
int w=0;//數(shù)組c的下標(biāo)
int v=0;//數(shù)組b的下標(biāo)
for(i=0;i<n;i++){
scanf("%d",&a[i]);
}
sort(a,a+n); //sort排序：低到高
if(n==1){? ? ? ?
printf("YES\n");? ? ?
printf("0\n");
printf("\n");
printf("1\n");
printf("%d\n",a[0]);
continue;
}
for(i=0;i<n-2;i++){
if(a[i]==a[i+1]){
if(a[i]==a[i+2]){//三個(gè)相同數(shù)的條件判斷
flag=1;
break;
}
}
}
if(flag==1){
printf("NO\n");//三個(gè)相同直接輸出No
continue;
}
else{
printf("YES\n");
}
for(i=0;i<n-1;i++){
if(a[i]!=a[i+1]){//無(wú)重復(fù)數(shù)字的情況
c[w]=a[i];//遞減序列
count1++;
w++;
if(i==n-2){? //序列最后一個(gè)數(shù)字渴频，不需要再加w
c[w]=a[i+1];
count1++;
}
}
else{? ? ? ? ? //有兩個(gè)重復(fù)數(shù)字
c[w]=a[i];
b[v]=a[i+1];//一個(gè)放到遞減一個(gè)到遞增芽丹，遞減先手
i++;
count1++;
count2++;
w++;
v++;
if(i==n-2){
c[w]=a[i+1];
count1++;
}
}
}
if(count2==0){? ? ? ? ? //無(wú)遞增數(shù)列
printf("0\n");
printf("\n");
}
else{? ? ? ? ? ? ? ? ? //有遞增數(shù)列 ，輸出
printf("%d\n",count2);
for(i=0;i<count2-1;i++)
printf("%d ",b[i]);
printf("%d\n",b[count2-1]);
}
//輸出： （遞減序列）
printf("%d\n",count1);
for(i=count1-1;i>0;i--)
printf("%d ",c[i]);
printf("%d\n",c[0]);
}
return 0;
}
大佬的代碼：可能我修煉還不夠吧
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000+5;
int main()
{
? ? int n; scanf("%d",&n);
? ? int vis[maxn]={0},a[maxn];
? ? int f=1;
? ? for(int i=0;i<n;i++){
? ? ? ? scanf("%d",&a[i]);
? ? ? ? vis[a[i]]++;
? ? ? ? if(vis[a[i]]>2) f=0;
? ? }
? ? if(f){
? ? ? ? puts("YES");
? ? ? ? sort(a,a+n);
? ? ? ? vector <int> v1,v2;
? ? ? ? v2.push_back(a[0]);
? ? ? ? for(int i=1;i<n;i++)
? ? ? ? ? ? if(a[i]==a[i-1]) v1.push_back(a[i]);
? ? ? ? ? ? else v2.push_back(a[i]);
? ? ? ? printf("%d\n",v1.size());
? ? ? ? for(int i=0;i<v1.size();i++)
? ? ? ? ? ? printf(i<v1.size()-1?"%d ":"%d",v1[i]);
? ? ? ? puts("");
? ? ? ? printf("%d\n",v2.size());
? ? ? ? for(int i=v2.size()-1;i>=0;i--)
? ? ? ? ? ? printf(i>0?"%d ":"%d\n",v2[i]);
? ? }
? ? else puts("NO");
? ? return 0;
}
