crazy_cloud's Blog
0%

Codeforces 702F T-Shirts

Posted on Edited on In

题目大意

给出 \(n\) 件 T-shirt 的质量 \(q_i\) 和花费 \(c_i\)，有 \(k\) 个人最开始分别有 \(b_i\) 的金钱。

每个人的选衣服的策略都是一样的：将所有 T-shirt 按照重要程度从大到小排序，重要程度相同的按花费从小到大排，然后每个人从头开始取 T-shirt，如果金钱数大于当前的 T-shirt 的花费，那么就买下这件衣服，问每个人最多能够买的 T-shirt 数量。

\(1\leq n,k\leq 2\times10^5\) \(1\leq q_i,c_i,b_i\leq 10^9\)

题目分析

直接按照一个一个人模拟难以下手。我们按照选取顺序来依次考虑每一件衣服然后一起处理所有人的情况。

使用一棵平衡树(Treap or Splay tree)来维护所有人当前以及买的衣服数量以及剩余的钱数，排序的关键字是剩余的钱数。

假设我们当前考虑到衣服花费为 \(c\)，那么我们就将平衡树 split 成小于 \(c\) 和大于等于 \(c\) 的两个部分，给第二个部分的答案打上加 \(1\) 的标记。

然后我们现在要维护买了这件衣服之后的平衡树，由于右边部分有的人的剩余价钱在买完这件衣服之后可能小于左边的最大值，我们并不能直接使用平衡树的合并算法。

怎么办呢？其实直接将右边部分买完后小于左边最大值的一个个加入到左边部分就行了。一个人（剩余钱数为 \(x\)）被加入到左边（设最大值为 \(a\)）当且仅当 \(x-c< a\)，我们又知道 \(a< c\)，于是有 \(x-c< c\)，也就是说 \(\frac x2< c\)。这意味着什么呢？一旦一个人被暴力从右边加入到左边，他的剩余钱数一定至少减少为原来的一半。因此，每个人最多只会被暴力插入 \(O(\log b)\) 次。实现的时候我们直接把右边部分小于 \(c\) 的暴力插入到左边效果和这样是一样的。

于是时间复杂度是 \(O(n \log k\log b)\) 的。

代码实现

其实做这题是为了突击学习 Treap（捂脸）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cctype>

using namespace std;

typedef unsigned int uint;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
	while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*f;
}

int buf[30];

inline void write(int x)
{
	if (x<0) putchar('-'),x=-x;
	for (;x;x/=10) buf[++buf[0]]=x%10;
	if (!buf[0]) buf[++buf[0]]=0;
	for (;buf[0];putchar('0'+buf[buf[0]--]));
}

const int N=200005;
const int Q=200005;

int ans[Q];

uint seed=0x12F81AC;

inline uint random_()
{
	seed^=seed<<13;
	seed^=seed>>17;
	seed^=seed<<5;
	return seed;
}

struct treap
{
	int son[Q][2],val[Q][2],tag[Q][2];//0 number 1 money
	uint fix[Q];

	inline void ADD(int rt,int delta,bool t){val[rt][t]+=delta,tag[rt][t]+=delta;}

	inline void clear(int rt)
	{
		if (!rt) return;
		for (int t=0;t<2;++t)
			if (tag[rt][t])
			{
				if (son[rt][0]) ADD(son[rt][0],tag[rt][t],t);
				if (son[rt][1]) ADD(son[rt][1],tag[rt][t],t);
				tag[rt][t]=0;
			}
	}

	int merge(int rt1,int rt2)
	{
		clear(rt1),clear(rt2);
		if (!(rt1&&rt2)) return rt1^rt2;
		int rt;
		if (fix[rt1]<fix[rt2]) son[rt1][1]=merge(son[rt1][1],rt2),rt=rt1;
		else son[rt2][0]=merge(rt1,son[rt2][0]),rt=rt2;
		return rt;
	}

	void split(int rt,int x,int &l,int &r)//v[l]<x v[r]>=x
	{
		if (!rt)
		{
			l=r=0;
			return;
		}
		clear(rt);
		int l_=0,r_=0;
		if (x<=val[rt][1]) split(son[rt][0],x,l_,r_),son[rt][0]=r_,l=l_,r=rt;
		else split(son[rt][1],x,l_,r_),son[rt][1]=l_,l=rt,r=r_;
	}

	inline void insert(int &rt,int np)
	{
		int l=0,r=0;
		split(rt,val[np][1],l,r),rt=merge(l,np),rt=merge(rt,r);
	}

	void heuristic_merge(int &rt1,int rt2)
	{
		if (!rt2) return;
		clear(rt2);
		int l=son[rt2][0],r=son[rt2][1];
		son[rt2][0]=son[rt2][1]=0;
		insert(rt1,rt2),heuristic_merge(rt1,l),heuristic_merge(rt1,r);
	}

	inline void getans(int rt)
	{
		if (!rt) return;
		clear(rt),ans[rt]=val[rt][0],getans(son[rt][0]),getans(son[rt][1]);
	}
}t;

struct t_shirts
{
	int cost,qlt;

	bool operator<(t_shirts const ts)const{return qlt>ts.qlt||qlt==ts.qlt&&cost<ts.cost;}
}tsrt[N];

int n,q,root;

void calc()
{
	for (int i=1,l,mid,r;i<=n;++i)
	{
		t.split(root,tsrt[i].cost,l,r);
		if (r) t.ADD(r,1,0),t.ADD(r,-tsrt[i].cost,1);
		t.split(r,tsrt[i].cost-1,mid,r),t.heuristic_merge(l,mid),root=t.merge(l,r);
	}
	t.getans(root);
}

int main()
{
	freopen("tshirts.in","r",stdin),freopen("tshirts.out","w",stdout);
	n=read();
	for (int i=1;i<=n;++i) tsrt[i].cost=read(),tsrt[i].qlt=read();
	sort(tsrt+1,tsrt+1+n);
	q=read();
	for (int i=1;i<=q;++i) t.val[i][1]=read(),t.fix[i]=random_(),t.insert(root,i);
	calc();
	for (int i=1;i<=q;++i) write(ans[i]),putchar(i<q?' ':'\n');
	fclose(stdin),fclose(stdout);
	return 0;
}