codeforces #413 B T-shirt buying (贪心)

题目链接

题意:有n个T恤,每个价格都不同,有三种颜色,分别用1,2,3表示,每件T恤给出前xiong和后背的颜色。现在有m个顾客排成一队,对于每个顾客,给出他喜欢的颜色,只要一个T恤的前xiong或者后背的颜色之一满足该颜色即可。顾客总希望买符合他喜欢颜色的T恤中价格最低的。现在问每个顾客买到的T恤的价格,如果某个顾客没有买T恤,输出-1

思路:贪一下?

对于每个颜色,找到价格最低的。记录的时候顺便记录id,以标记某件有2个颜色的衣服是否卖出去了。

1A美滋滋

/* ***********************************************
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}