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).
您将得到一个由nn整数组成的数组aa。您可以执行以下操作任意次数（可能为零）：选择一对指数（i，j）（i，j），使i−j=1 i−j=1（指数i i和j j相邻），并设置a i：=a i+a i−a j a i：=a i+a i−a j选择一对指数（i，j）（i，j），使i−j=1 i−j=1（指数i i和j j相邻），并设置a i：=a i−a i−a j a i：=a i−a i−a j。数值x x表示x x的绝对值。例如，4=4 4=4，−3=3−3=3。您的任务是找到获取相等元素数组所需的最小操作数，并打印操作顺序。它保证您总是可以使用这些操作获得相等元素的数组。注意，每次操作后，当前数组的每个元素的绝对值不应超过10181018。输入输入的第一行包含一个整数n n（1≤n≤2 1051≤n≤2 105）——aa中的元素数。输入的第二行包含nn整数a1，a2，…，an a1，a2，…，an（0≤ai≤2 1050≤ai≤2 105），其中ai ai是aa的第二个元素。产量在第一行中，打印一个整数kk——获得相等元素数组所需的最小操作数。在下一个KK行中，打印操作本身。pp th操作应打印为整数的三倍（tp，ip，jp）（tp，ip，jp），其中tp tp是11或22（11表示执行第一种类型的操作，22表示执行第二种类型的操作），ip ip和jjp是数组相邻元素的索引，这样1≤ip，jp≤n1≤ip，jp≤n，ip−jp|=1 ip−jp=1.请参阅示例以获得更好的理解。注意，每次操作后，当前数组的每个元素的绝对值不应超过10181018。如果有许多可能的答案，您可以打印任何答案。
大意就是给你一个数组，问能否让每个元素进入递增或递减序列，最后形成一个严格递减和递增的序列。
我的理解：
就是给一个序列，如有三次重复数字，则输出No
如不重复，则要分成递增，递减数组，然后原序列中如果没有重复（只重复两次）就全给递减序列，如果有重复，重复的递增给递增序列。
网上找的并理解的代码
#include<stdio.h>#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
int a[200005];//用来存合成序列
int b[200005];//用来存递增序列
int c[200005];//用来存递减序列
int main(){
int n;
int i;
while(scanf("%d",&n)!=EOF){
int count1=0;//用来存递减序列的个数
int count2=0;//用来存递增序列的个数
int flag=0;//用来判断数组中是否有三个相同的数
int w=0;//数组c的下标
int v=0;//数组b的下标
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]){//三个相同数的条件判断
flag=1;
break;
}
}
}
if(flag==1){
printf("NO\n");//三个相同直接输出No
continue;
}
else{
printf("YES\n");
}
for(i=0;i<n-1;i++){
if(a[i]!=a[i+1]){//无重复数字的情况
c[w]=a[i];//递减序列
count1++;
w++;
if(i==n-2){ //序列最后一个数字，不需要再加w
c[w]=a[i+1];
count1++;
}
}
else{ //有两个重复数字
c[w]=a[i];
b[v]=a[i+1];//一个放到递减一个到递增，递减先手
i++;
count1++;
count2++;
w++;
v++;
if(i==n-2){
c[w]=a[i+1];
count1++;
}
}
}
if(count2==0){ //无递增数列
printf("0\n");
printf("\n");
}
else{ //有递增数列 ，输出
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;
}
网友评论