首页 > 代码库 > cf Make It Nondeterministic （简单贪心）
cf Make It Nondeterministic （简单贪心）
有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 （简单贪心）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。