题目链接:http://codeforces.com/problemset/problem/472/C
题目意思:给出 n 个 people(从第1行往下数,编号依次为1,2,...,n),每 个 people 由 first name 和 last name 组成,每个people用他自己的first name 或者是 last name 是不确定的。现在给出p1, p2, ..., pn 这个排列,问按照这个顺序排列能否满足字典序逐渐增加。
思路不难得出。对于第 pi+1 这个人,只要选择比前一个人,即 pi的字典序大的name即可,由于要保证后面的pj (i < j)尽可能满足条件,我们只需要选择较小的那个name,但也要比前一个人的name要大。这个操作可以先 min(f[p], s[p]),如果比前一个人的name要小,我们才选择max(f[p], s[p])
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std; const int maxn = 1e5 + ; string f[maxn], s[maxn];
string select[maxn]; int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif int n, p;
while (scanf("%d", &n) != EOF)
{
for (int i = ; i <= n; i++)
cin >> f[i] >> s[i];
scanf("%d", &p); select[] = min(f[p], s[p]);
bool flag = true;
for (int i = ; i <= n; i++)
{
scanf("%d", &p);
select[i] = min(f[p], s[p]);
if (select[i] < select[i-] && flag)
select[i] = max(f[p], s[p]);
if (select[i] < select[i-] && flag)
flag = false;
}
printf("%s\n", flag ? "YES" : "NO");
}
return ;
}