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

Posted by 111qqz on Friday, May 12, 2017

TOC

题目链接

题意:有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
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define PB push_back
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=2E5+7;
int n,m;
bool vis[N]; //表示某个id的是否被卖出。
vector< pair<int,int>>v[4]; //pair<price,id>,id是为了标记是否卖出去了,卖出去就继续找下一个。
                    //虽然价格本身唯一,但是太大不适合做标记?
struct node
{
    int p,a,b;
    int id;
}A[N];

bool cmp(node x,node y)
{
    return x.p<y.p;
}
vector<int>ans;
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif
    ms(vis,false);
    scanf("%d",&n);
    for ( int i = 1 ; i <= n ; i++) scanf("%d",&A[i].p);
    for ( int i = 1 ; i <= n ; i++) scanf("%d",&A[i].a);
    for ( int i = 1 ; i <= n ; i++) scanf("%d",&A[i].b);
    for ( int i = 1 ; i <= n ; i++) A[i].id = i;
    //sort(A+1,A+n+1,cmp); //价格升序 没有必要吧。。。
	
    for ( int i = 1 ; i <= n ; i++)
    {
        int a = A[i].a;
        int b = A[i].b;
        int p = A[i].p;
        int id = A[i].id;
        if (a==b)
        {
        v[a].push_back(make_pair(p,id));
        }else
        {
        v[a].push_back(make_pair(p,id));
        v[b].push_back(make_pair(p,id));
        }
    }



    sort(v[1].begin(),v[1].end());
    sort(v[2].begin(),v[2].end());
    sort(v[3].begin(),v[3].end());
    scanf("%d",&m);
    //cout<<"m:"<<m<<endl;
    int p[4]={0};
    int mm = m;
    while (m--)
    {
        int x;
        scanf("%d",&x);
        while (p[x]<v[x].size()&&vis[v[x][p[x]].second]) p[x]++;
        if (p[x]==v[x].size())
        {
        ans.push_back(-1);
        }
        else
        if (!vis[v[x][p[x]].second])
        {
        vis[v[x][p[x]].second] = true;
        ans.push_back(v[x][p[x]].first);
        }
    }
    m = mm;
    for ( int i = 0 ; i < m ; i++)
        printf("%d%c",ans[i],i==m-1?'\n':' ');
	


  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付