有N个人。每个人都有两个名字。
给出这N个人的一个排列。p[1]...p[N]。
现在让每个人挑自己丙个名字中的一个名字。问是否存在一种方案，使得挑出来的N个名字按字典序排完以后正好是p[1]...p[N]。
思路：
按照p[1]..p[N]的顺序挑第p[i]个人名字中小的（要大于第p[i-1]个人挑出来的名字），若不行，则挑另一个。若另一个名字也不大于第p[i-1]个人挑出来的名字，就输出NO。
不多说，直接看代码。
代码：
int n; string name1[100005]; string name2[100005]; string cun[100005]; int p[100005]; int main(){ scanf("%d",&n); rep(i,1,n){ cin>>name1[i]>>name2[i]; } rep(i,1,n){ scanf("%d",&p[i]); if(i==1){ if(name1[p[i]]<name2[p[i]]) cun[1]=name1[p[i]]; else cun[1]=name2[p[i]]; }else{ bool ok=false; if(name1[p[i]]<name2[p[i]]){ if(name1[p[i]]>cun[i-1]){ ok=true; cun[i]=name1[p[i]]; } else if(name2[p[i]]>cun[i-1]){ ok=true; cun[i]=name2[p[i]]; } }else{ if(name2[p[i]]>cun[i-1]){ ok=true; cun[i]=name2[p[i]]; } else if(name1[p[i]]>cun[i-1]){ ok=true; cun[i]=name1[p[i]]; } } if(!ok){ printf("NO\n"); return 0; } } } printf("YES\n"); }
cf Make It Nondeterministic （简单贪心）
原文：http://www.cnblogs.com/fish7/p/4001224.html