【CF799B】T-shirt buying（一道很水的小根堆）

点此看题面

大致题意： 有\(n\)件T恤衫，告诉你每件T恤衫的价格以及它正面和反面的颜色（\(1≤\)颜色的编号\(≤3\)），现在有m个顾客，已知每个人想要的衣服的颜色（一件T恤衫只要有一面的颜色满足他的需求即可），请你求出每个人所需支付的最低价格（一件T恤衫只能被买一次）。

题解

由于这道题的颜色最多只有\(3\)种，因此，我们只要开\(3\)个小根堆来存储每种颜色的衣服的价格和编号（价格为第一关键字）即可。

由于每件衣服只能被买一次，因此当一件衣服被买走之后，我们可以给它打个标记表示它已被买走，下次再遇到它时就可以直接跳过它了。

代码

#include<bits/stdc++.h>

#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)<(y)?(x):(y))

#define N 200000

using namespace std;

int n,Q,del[N+5];

struct clothes

{

	int a,b,pos,Price;

	bool operator < (const clothes a) const

	{

		return Price>a.Price;

	}

}s[N+5];

priority_queue<clothes> h[4];

inline char tc()

{

	static char ff[100000],*A=ff,*B=ff;

	return A==B&&(B=(A=ff)+fread(ff,1,100000,stdin),A==B)?EOF:*A++;

}

inline void read(int &x)

{

	x=0;char ch;

	while(!isdigit(ch=tc()));

	while(x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc()));

}

inline void write(int x)

{

	if(x>9) write(x/10);

	putchar(x%10+'0');

}

int main()

{

	register int i;

	for(read(n),i=1;i<=n;++i) read(s[i].Price);

	for(i=1;i<=n;++i) read(s[i].a),s[i].pos=i;

	for(i=1;i<=n;++i) read(s[i].b),h[s[i].a].push(s[i]),h[s[i].b].push(s[i]);

	for(read(Q);Q;--Q)

	{

		int x;read(x);

		while(!h[x].empty()&&del[h[x].top().pos]) h[x].pop();//若当前的衣服已被买走，则直接跳过它

		if(h[x].empty()) putchar('-'),putchar('1'),putchar(' ');//如果堆已空，说明没有这种颜色的衣服了，输出-1

		else write(h[x].top().Price),putchar(' '),del[h[x].top().pos]=1,h[x].pop();//输出答案，并标记这件衣服已被买走

	}

	return 0;

}

巴特西

【CF799B】T-shirt buying（一道很水的小根堆）

题解

代码

最新文章

热门文章