codeforces #413 B T-shirt buying (贪心)
题意：有n个Ｔ恤，每个价格都不同，有三种颜色，分别用1,2,3表示，每件Ｔ恤给出前xiong和后背的颜色。现在有m个顾客排成一队，对于每个顾客，给出他喜欢的颜色，只要一个Ｔ恤的前xiong或者后背的颜色之一满足该颜色即可。顾客总希望买符合他喜欢颜色的Ｔ恤中价格最低的。现在问每个顾客买到的Ｔ恤的价格，如果某个顾客没有买Ｔ恤，输出-1
思路：贪一下？
对于每个颜色，找到价格最低的。记录的时候顺便记录id，以标记某件有２个颜色的衣服是否卖出去了。
１A美滋滋
/* ***********************************************
Author :111qqz
Created Time :2017年05月11日 星期四 15时29分58秒
File Name :B.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=2E5+7;
7int n,m;
8bool vis[N]; //表示某个id的是否被卖出。
9vector< pair<int,int>>v[4]; //pair<price,id>,id是为了标记是否卖出去了，卖出去就继续找下一个。
10 //虽然价格本身唯一，但是太大不适合做标记？
11struct node
12{
13 int p,a,b;
14 int id;
15}A[N];
1bool cmp(node x,node y)
2{
3 return x.p<y.p;
4}
5vector<int>ans;
6int main()
7{
8 #ifndef ONLINE_JUDGE
9 freopen("code/in.txt","r",stdin);
10 #endif
11 ms(vis,false);
12 scanf("%d",&n);
13 for ( int i = 1 ; i <= n ; i++) scanf("%d",&A[i].p);
14 for ( int i = 1 ; i <= n ; i++) scanf("%d",&A[i].a);
15 for ( int i = 1 ; i <= n ; i++) scanf("%d",&A[i].b);
16 for ( int i = 1 ; i <= n ; i++) A[i].id = i;
17 //sort(A+1,A+n+1,cmp); //价格升序 没有必要吧。。。
1 for ( int i = 1 ; i <= n ; i++)
2 {
3 int a = A[i].a;
4 int b = A[i].b;
5 int p = A[i].p;
6 int id = A[i].id;
7 if (a==b)
8 {
9 v[a].push_back(make_pair(p,id));
10 }else
11 {
12 v[a].push_back(make_pair(p,id));
13 v[b].push_back(make_pair(p,id));
14 }
15 }
1 sort(v[1].begin(),v[1].end());
2 sort(v[2].begin(),v[2].end());
3 sort(v[3].begin(),v[3].end());
4 scanf("%d",&m);
5 //cout<<"m:"<<m<<endl;
6 int p[4]={0};
7 int mm = m;
8 while (m--)
9 {
10 int x;
11 scanf("%d",&x);
12 while (p[x]<v[x].size()&&vis[v[x][p[x]].second]) p[x]++;
13 if (p[x]==v[x].size())
14 {
15 ans.push_back(-1);
16 }
17 else
18 if (!vis[v[x][p[x]].second])
19 {
20 vis[v[x][p[x]].second] = true;
21 ans.push_back(v[x][p[x]].first);
22 }
23 }
24 m = mm;
25 for ( int i = 0 ; i < m ; i++)
26 printf("%d%c",ans[i],i==m-1?'\n':' ');
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}