C - Design Tutorial: Make It Nondeterministic

模拟 c++

题目大意：

    每个人可以选择first name 或者 last name 当自己的账号，问能不能实现给定的字典序排位。

解题思路：

    cur用于记录上一个人选择的账号。第一个人肯定要选择last name和first name里最小的，记为cur第二个人，如果其中小的比cur大，那么就选择那个。如果比cur小，那么再次比较较大的和cur，如果还是比cur小，这个排序不能进行了。以此类推。
    时间复杂度O(1)，空间复杂度O(1)。

AC代码：

#include<iostream>  
#include<cstdio>  
#include<algorithm>  
#include<cstring>  
#include<string>  
#include<cmath>  
#include<cstdlib>  
using namespace std;  
int N;  
string a[100100],b[100100];  
string cur="";  
int p[100100];  
int main()  
{  
    int i,x;  
    scanf("%d",&N);
    for(i=0;i<N;i++)   
    {  
        scanf("%s %s",a[i],b[i]); 
    }  
    for(i=0;i<N;i++)  
    {  
        scanf("%d",p[i]);  
        p[i]--;  
    }  
    for(i=0;i<N;i++)  
    {  
        x=p[i];  
        if(a[x]>b[x])  
        {  
            swap(a[x],b[x]);  
        }  
        if(cur<a[x])  
        {  
            cur=a[x];  
        }  
        else if(cur<b[x])   
        {  
            cur=b[x];  
        }  
        else  
        {  
            printf("NO");  
            return 0;  
        }  
    }  
    printf("YES");
    return 0;  
}