题意是：给你一个1-n的排列，要你把这个排列分成两个序列，且这个两个序列都满足单调性。
题解：
1.首先假设找出的两个序列都是单调递增的（都是单调递减的同理）
那么很容易可以想到,将新加入的数放入到某个序列尾端，使得另一个序列尾端的数尽量小。
2.如果最后的两个序列为一个递增一个递减。
这种情况下，有一种眼光稍微长远一些的贪心策略。
假设当前要加入的数g[x],如果g[x]既可以放入单增序列中也可以放入单减序列中，则与g[x+1]比较。
if(g[x]>g[x+1]) 把g[x]放入单减序列中
else 把g[x]放入单增序列中
为什么这样贪心就行了？
可以做一个假设，当g[x]>g[x+1]，我们却把g[x]放入单增序列中，则g[x]只能放入单减序列，最后得出的两个序列的尾部为:
xxxxg[x] (单增序列) 。。。。。。。。。方法一
xxxxxxg[x+1] (单减序列)
而当我们把g[x]放入单减序列时，此时g[x+1]可能放入单增序列中，一定可以放入单减序列中，
1.如果g[x+1] 放入单减序列中，得出两个序列尾部为：
xxxX （单增序列） 。。。。。。。。。方法二
xxxxxxg[x]g[x+1] (单减序列)
而X<g[x] ，所以下面这种方法得出的结果一定优于方法一。
2.如果g[x+1]能放入单增序列，放入其中得出的两个序列尾部为：
xxxxg[x+1] (单增序列) 。。。。。。。。。方法三
xxxxxxg[x] (单减序列)
因为g[x]>g[x+1],所以结果一定优于方法一。
把眼界放开，即使是贪心也能贪的漂亮!
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define maxN 100005 const int inf=~0U>>1; int s1[maxN]; int f[maxN][2]; int N,len1,len2; bool judge1() { f[0][0]=f[0][1]=-1; len1=len2=0; for(int i=1;i<=N;i++) { if(s1[i]<f[len1][0]&&s1[i]<f[len2][1]) return false; else if(s1[i]>f[len1][0]&&s1[i]<f[len2][1]) f[++len1][0]=s1[i]; else if(s1[i]<f[len1][0]&&s1[i]>f[len2][1]) f[++len2][1]=s1[i]; else { if(f[len2][1]>f[len1][0]) f[++len2][1]=s1[i]; else f[++len1][0]=s1[i]; } } if(len1==N) f[++len2][1]=f[len1--][0]; return true; } bool judge2() { f[0][0]=f[0][1]=inf; len1=len2=0; for(int i=1;i<=N;i++) { if(s1[i]>f[len1][0]&&s1[i]>f[len2][1]) return false; else if(s1[i]>f[len1][0]&&s1[i]<f[len2][1]) f[++len2][1]=s1[i]; else if(s1[i]<f[len1][0]&&s1[i]>f[len2][1]) f[++len1][0]=s1[i]; else { if(f[len2][1]<f[len1][0]) f[++len2][1]=s1[i]; else f[++len1][0]=s1[i]; } } if(len1==N) f[++len2][1]=f[len1--][0]; return true; } bool judge3() { len1 = len2 = 0; f[len1][0]=-1; f[len2][1]=inf; for(int i=1;i<=N;i++) { if(s1[i]<f[len1][0]&&s1[i]>f[len2][1]) return false; else if(s1[i]>f[len1][0]&&s1[i]<f[len2][1]) { if(i==N) f[++len1][0]=s1[i]; else if(s1[i+1]>s1[i]) f[++len1][0]=s1[i]; else f[++len2][1]=s1[i]; } else if(s1[i]>f[len1][0]) f[++len1][0]=s1[i]; else f[++len2][1]=s1[i]; } return true; } int main() { scanf("%d",&N); for(int i=1,j=N;i<=N;i++,j--) { scanf("%d",&s1[i]); } if(judge1()) { printf("%d %d ",len1,len2); for(int i=1;i<=len1;i++) printf("%d%c",f[i][0],i==len1?' ':' '); for(int i=1;i<=len2;i++) printf("%d%c",f[i][1],i==len2?' ':' '); return 0; } if(judge2()) { printf("%d %d ",len1,len2); for(int i=1;i<=len1;i++) printf("%d%c",f[i][0],i==len1?' ':' '); for(int i=1;i<=len2;i++) printf("%d%c",f[i][1],i==len2?' ':' '); return 0; } if(judge3()) { printf("%d %d ",len1,len2); for(int i=1;i<=len1;i++) printf("%d%c",f[i][0],i==len1?' ':' '); for(int i=1;i<=len2;i++) printf("%d%c",f[i][1],i==len2?' ':' '); return 0; } printf("Fail "); //print1(dp1[len1]); //printf(" "); //print2(dp2[len2]); return 0; }
另加一个，我自己想的丑陋的贪心。。。
// // main.cpp // timus1965 // // Created by 陈加寿 on 16/3/16. // Copyright © 2016年 chenhuan001. All rights reserved. // #include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <vector> #include <map> #include <set> #include <math.h> #include <algorithm> using namespace std; #define N 100100 int g[N],tg[N]; int ans1[N],ans2[N]; int cnt1,cnt2; int n; int b1,d1,b2,d2; int fuc() { cnt1 = cnt2 =0; //-> ans2[0] = 0; ans1[ ++cnt1 ] = g[1]; for(int i=2;i<=n;i++) { if(g[i]<ans1[cnt1] && g[i]<ans2[cnt2]) { return 0; } //否则选尽量大的一边 if(g[i]>ans1[cnt1]) ans1[++cnt1]=g[i]; else ans2[++cnt2]=g[i]; } return 1; } int fuc1() { cnt1 = cnt2 =0; //<- ans2[0] = n+1; ans1[ ++cnt1 ] = g[1]; for(int i=2;i<=n;i++) { if(g[i]>ans1[cnt1] && g[i]>ans2[cnt2]) { return 0; } //否则选尽量小的一边 if(g[i]<ans1[cnt1]) ans1[++cnt1]=g[i]; else ans2[++cnt2]=g[i]; } return 1; } int test1(int b,int d) { if( tg[d]<b1 || tg[d]>d1 ) return 0;// g[i]无法放入ans1中 //把(b,d)间的数全部放入ans2中去 //首先保证(b,d)之间是递减的 if(b+1 == d) { ans1[++cnt1] = d; b1 = tg[d]; return 1; } for(int i=d-2;i>b;i--) { if(tg[i]<tg[i+1]) return 0;//并不递减 } if( tg[d-1]>b2 && tg[b+1]<d2 ) { for(int i=d-1;i>b;i--) ans2[++cnt2] = i; ans1[++cnt1] = d; d2=tg[d-1]; b1 = tg[d]; return 1; } else return 0; } int test2(int b,int d) { if(tg[b]<b2 || tg[b]>d2) return 0; if(b+1 == d) { ans2[++cnt2] = b; b2 = tg[b]; return 1; } for(int i=b+1;i<d-1;i++) { if(tg[i]>tg[i+1]) return 0; } if(tg[b+1]>b1 && tg[d-1]<d1) { for(int i=d-1;i>b;i--) ans1[++cnt1] = i; ans2[++cnt2] = b; d1 = tg[b+1]; b2 = tg[b]; return 1; } else return 0; } int solve() { int b=0,d=n+1; b1=0,d1=n+1; b2=0,d2=n+1; //并不需要set for(int i=1;i<=n;i++) { if( g[i]<b || g[i]>d) continue; //已经处理过的，不再处理 if(g[i]-b < d-g[i]) { //靠左,g[i]放入ans1中 if( test1(b,g[i])==1 ) { //如果 b = g[i]; } else if(test2(g[i],d)==1) { d = g[i]; } else return 0;//两个测试都不过 直接返回不行. } else { //靠右 if(test2(g[i],d)==1) { d=g[i]; } else if(test1(b, g[i])==1) { b=g[i]; } else return 0; } } return 1; } int cmp(int x,int y) { return x>y; } int main() { cin>>n; for(int i=1;i<=n;i++) { scanf("%d",g+i); tg[ g[i] ] = i; } g[0]=0; g[n+1]=n+1; tg[0]=0; tg[n+1]=n+1; cnt1 = cnt2 = 0; int flag=0; //step one tha same direction if( fuc() || fuc1() ) { flag=1; } if(flag == 0) { // step two the different direction cnt1 = cnt2 =0; flag = solve(); //最后再sort一下 sort(ans1+1,ans1+1+cnt1); sort(ans2+1,ans2+1+cnt2,cmp); } if(flag == 0) { printf("Fail "); } else { //输出答案 if(cnt1==n) { ans2[++cnt2] = ans1[cnt1--]; } if(cnt2==n) { ans1[++cnt1] = ans2[cnt2--]; } cout<<cnt1<<" "<<cnt2<<endl; for(int i=1;i<=cnt1;i++) printf("%d ",ans1[i]); printf(" "); for(int i=1;i<=cnt2;i++) printf("%d ",ans2[i]); printf(" "); } return 0; }