链接:http://codeforces.com/contest/799/problem/B

题意：

给定n件衣服，对于第i（1<i<=n）件衣服，分别有价格pi，前颜色ai,后颜色bi三个值。然后有m个顺序访问店铺的顾客，每位顾客有一个最喜欢的颜色，只要衣服有一面是他们最喜欢的颜色，他们就会买下这些衣服中最便宜的一件，分别求出每个顾客购买时的价格，如果没有衣服是他们最喜欢的颜色就输出-1。 n，m <= 2e5。

分析：

一开始做的时候看到时间限制3s，直接sort加对于m次询问的O(n)匹配，复杂度为nlogn+m*n，超时。

然后发现这题数据查找的复杂度应该更低才能过， 所以选用了set作为数据结构， 对于set，每次操作都是logn， 平均下来应该是nlogn + mlogn的复杂度，参考了tourist的代码，终于A了。

具体操作是开一个vis去标记哪些衣服被买过。

开3个颜色的set<pair<int,int> s[color]，，然后把符合衣服的价钱和编号号作为一对pair插入,这时候set是按pair的first元素排序的。

每次都取x = s[color].begin().second(这个x的含义是，符合条件的最便宜衣服的编号)，删除这个颜色set中的这个元素，如果能操作说明里面有元素，否则输出-1。

然后判断这个x代表的衣服是否已经被购买过，如果没有就输出这件价钱，标记为已购买，否则重复取取x = s[color].begin().second，直到输出或者元素被删完，删除其实是因为为了找下一个最小值。

 

#include 
     
      using namespace std;const int maxn = 1e6;int p[maxn], a[maxn], b[maxn];int n, m;set < pair 
      
        > s[7];bool vis[maxn];int main(){    //freopen("1.txt","r",stdin);    scanf("%d", &n);    for(int i = 0; i < n; i++)    {        scanf("%d", &p[i]);    }    for(int i = 0; i < n; i++)    {        scanf("%d", &a[i]);    }    for(int i = 0; i < n; i++)    {        scanf("%d", &b[i]);    }    for(int i = 0; i < n; i++)    {        s[a[i]].insert(make_pair(p[i],i));//这个make_pair有点像初始化列表，就是把两个值构成pair然后insert到set中。        s[b[i]].insert(make_pair(p[i],i));//这是将一对 
       <价格,编号>
        的pair插入set，set按first（第一个元素——价格）排序    }    scanf("%d", &m);    memset(vis,0,sizeof(vis));    while(m--)    {        int t,ans = -1;        scanf("%d", &t);        while(!s[t].empty())        {            int x = (*(s[t].begin())).second;            s[t].erase(s[t].begin());            if(vis[x])            {                continue;            }            vis[x] = 1;            ans = p[x];            break;        }        printf("%d ", ans);    }    puts("");    return 0;}