BZOJ1503 [NOI2004]郁闷的出纳员

发表于 更新于 阅读次数： 本文字数： 1.9k 阅读时长 ≈ 2 分钟

声明

刚开始学平衡树，并不会写。而且这题可以用pb_ds通过，这里给出这种版本。

代码

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
#include<bits/stdc++.h>
#include<bits/extc++.h>
//extc++.h与stdc++.h类似，后者包含标准C++的头文件，而前者提供扩展
using namespace std;
using namespace __gnu_pbds;
//pb_ds所需的namespace
const int M=100005;
typedef pair<int,int> pii;
//first存工资，second存id（可能有重复的工资，需要区分）
typedef tree<pii,null_type,greater<pii>,rb_tree_tag,tree_order_statistics_node_update> tree_t;
//使用tree_order_statistics_node_update来获取find_by_order方法
tree_t T,TE;
//TE为无用的树
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	int delta=0,ans=0,id=0;
  	//delta保存全局工资偏移
	while(n--)
	{
		char opt;
		for(opt=getchar();isspace(opt);opt=getchar());
      	//跳过空白
		int x;
		scanf("%d",&x);
		switch(opt)
		{
			case 'I':
				if(x>=m)
					T.insert(make_pair(x-delta,++id));
            		//插入时需考虑偏移
				break;
			case 'A':
				delta+=x;
				break;
			case 'S':
				delta-=x;
				T.split(make_pair(m-delta,0),TE);
            	//清空TE，并把T中工资小于最低标准的移动到TE中
				ans+=TE.size();
				break;
			case 'F':
				tree_t::iterator i=T.find_by_order(x-1);
            	//注意find_by_order是从0开始的
				if(i==T.end())
					puts("-1");
				else
					printf("%d\n",i->first+delta);
		}
	}
	printf("%d\n",ans);
	return 0;
}

奇怪的I/O问题

用cin/cout会超时，这很正常；但是当我试图用

1
scanf("%1s%d",&opt,&x);

输入opt时出现了问题：主站40分，大牛0分，用%s也不行。也许是这样有问题，欢迎反馈。

修正：使用scanf()输入字符串数组大小至少为strlen+1。

正确方法：

1
2
char opt[2];
scanf("%1s",opt);

总结

合理使用pb_ds能简化代码，但pb_ds也有很多缺点：

  • 常数大（虽然比STL小）

  • 相比手写数据结构局限

  • 在比赛中用不安全？

  • 不同版本的兼容性问题，如null_type和null_mapped_type（旧版）

  • 调试不方便

    当我试图(gdb)print一个tree时，出现一堆乱七八糟的内容。这里提供一个简单的调试方法：

1
2
3
4
5
void debug(const tree_t& T)
{
	for(tree_t::iterator i=T.begin();i!=T.end();i++)
		cout<<i->first<<' '<<i->second<<endl;
}

或者C++11

1
2
3
4
5
void debug(const tree_t& T)
{
	for(auto i:T)
		cout<<i.first<<' '<<i.second<<endl;
}

这样只要执行类似(gdb)p debug(T)就能打印出来