codeforces #413 B T-shirt buying (贪心)
题意：有n个Ｔ恤，每个价格都不同，有三种颜色，分别用1,2,3表示，每件Ｔ恤给出前xiong和后背的颜色。现在有m个顾客排成一队，对于每个顾客，给出他喜欢的颜色，只要一个Ｔ恤的前xiong或者后背的颜色之一满足该颜色即可。顾客总希望买符合他喜欢颜色的Ｔ恤中价格最低的。现在问每个顾客买到的Ｔ恤的价格，如果某个顾客没有买Ｔ恤，输出-1
思路：贪一下？
对于每个颜色，找到价格最低的。记录的时候顺便记录id，以标记某件有２个颜色的衣服是否卖出去了。
１A美滋滋
1/* ***********************************************
2Author :111qqz
3Created Time :2017年05月11日 星期四 15时29分58秒
4File Name :B.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=2E5+7;
35int n,m;
36bool vis[N]; //表示某个id的是否被卖出。
37vector< pair<int,int>>v[4]; //pair<price,id>,id是为了标记是否卖出去了，卖出去就继续找下一个。
38 //虽然价格本身唯一，但是太大不适合做标记？
39struct node
40{
41 int p,a,b;
42 int id;
43}A[N];
44
45bool cmp(node x,node y)
46{
47 return x.p<y.p;
48}
49vector<int>ans;
50int main()
51{
52 #ifndef ONLINE_JUDGE
53 freopen("code/in.txt","r",stdin);
54 #endif
55 ms(vis,false);
56 scanf("%d",&n);
57 for ( int i = 1 ; i <= n ; i++) scanf("%d",&A[i].p);
58 for ( int i = 1 ; i <= n ; i++) scanf("%d",&A[i].a);
59 for ( int i = 1 ; i <= n ; i++) scanf("%d",&A[i].b);
60 for ( int i = 1 ; i <= n ; i++) A[i].id = i;
61 //sort(A+1,A+n+1,cmp); //价格升序 没有必要吧。。。
62
63 for ( int i = 1 ; i <= n ; i++)
64 {
65 int a = A[i].a;
66 int b = A[i].b;
67 int p = A[i].p;
68 int id = A[i].id;
69 if (a==b)
70 {
71 v[a].push_back(make_pair(p,id));
72 }else
73 {
74 v[a].push_back(make_pair(p,id));
75 v[b].push_back(make_pair(p,id));
76 }
77 }
78
79
80
81 sort(v[1].begin(),v[1].end());
82 sort(v[2].begin(),v[2].end());
83 sort(v[3].begin(),v[3].end());
84 scanf("%d",&m);
85 //cout<<"m:"<<m<<endl;
86 int p[4]={0};
87 int mm = m;
88 while (m--)
89 {
90 int x;
91 scanf("%d",&x);
92 while (p[x]<v[x].size()&&vis[v[x][p[x]].second]) p[x]++;
93 if (p[x]==v[x].size())
94 {
95 ans.push_back(-1);
96 }
97 else
98 if (!vis[v[x][p[x]].second])
99 {
100 vis[v[x][p[x]].second] = true;
101 ans.push_back(v[x][p[x]].first);
102 }
103 }
104 m = mm;
105 for ( int i = 0 ; i < m ; i++)
106 printf("%d%c",ans[i],i==m-1?'\n':' ');
107
108
109
110 #ifndef ONLINE_JUDGE
111 fclose(stdin);
112 #endif
113 return 0;
114}