P2286[HNOI2004]题解

发表于 | 分类于 |
字数统计: 1.3k 字 | 阅读时长 ≈ 20 分钟

这道题目可以算是一道set的板子题（在CJC大佬的提醒下恍然大悟，CJC的博客），于是这篇题解某种意义上其实是对于set的讲解和复习。关于STL的话，全称为Standard Template Library，说白了就是一个非常多功能的库，引用时按情况引用，可能会有set map algorithm等等，按情况来分析，用途很多，有封装好的快排、大根小根堆（优先队列）、二分查找、全排列、各种神仙玩意儿。set则是其中的一个工具。

Set

set和multiset的区别是，后者可以有重复的元素，前者不可以。
set插入重复元素可能会不成功，所以有重复元素要用multiset。
用法：

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
#include <iostream>
#include <cstdio>
#include <set> //set所在的库

using namespace std;

int main()
{
	set<int> st; //定义方法，其他类型类似
	int a[10] = {1, 2, 3, 8, 7, 7, 5, 6, 8, 12};
	for (int i = 1; i < 10; ++i)
		st.insert(a[i]);//插入方式
	cout << st.size() << endl; //st.size()返回这个set的大小，整形
	set<int>::iterator i; //迭代器，类似于一个指向set中某个元素的指针，不可以比较大小，不可以相加相减，但可以++i（迭代）
	for (i = st.begin(); i != st.snd(); ++i) //由于迭代器的特殊性，只能用这种方式进行循环
		cout << * i << ","; 
	cout endl;
	pair<set<int>::iterator, bool> result = st.insert(2);
	if (!result.second)
		cout << * result.first << " already exists." << endl;
	else
		cout << * result.first << " inserted." << endl;

	return 0;
}

更多的关于set的用法和函数详解，可以访问C++ reference

这道题目

题目简述：
凡凡开了一间宠物收养场。收养场提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。

每个领养者都希望领养到自己满意的宠物，凡凡根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值（是一个正整数，），而他也给每个处在收养场的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了，宠物收养场总是会有两种情况发生：被遗弃的宠物过多或者是想要收养宠物的人太多，而宠物太少。

被遗弃的宠物过多时，假若到来一个领养者，这个领养者希望领养的宠物的特点值为，那么它将会领养一只目前未被领养的宠物中特点值最接近的一只宠物。（任何两只宠物的特点值都不可能是相同的，任何两个领养者的希望领养宠物的特点值也不可能是一样的）如果有两只满足要求的宠物，即存在两只宠物他们的特点值分别为和，那么领养者将会领养特点值为的那只宠物。

收养宠物的人过多，假若到来一只被收养的宠物，那么哪个领养者能够领养它呢？能够领养它的领养者，是那个希望被领养宠物的特点值最接近该宠物特点值的领养者，如果该宠物的特点值为，存在两个领养者他们希望领养宠物的特点值分别为和，那么特点值为的那个领养者将成功领养该宠物。

一个领养者领养了一个特点值为的宠物，而它本身希望领养的宠物的特点值为，那么这个领养者的不满意程度为。

你得到了一年当中，领养者和被收养宠物到来收养所的情况，请你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时，收养所里面既没有宠物，也没有领养者。

问题解决：

知道了set怎么用，辣么就好办了（好像还要知道一个lower_bound()）

我们只要把每次宠物的编号插入，然后直接查询，查询的话也是用STL中的lower_bound和uper_bound，然后这道题目就可以A了

代码如下

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

#include <bits/stdc++.h> //万能头文件

using namespace std;

const int MAXN = 1000010;
const int MAX_INT = 1e9;

int n, ans;
set<int> s; //定义set

void find(int x) 
{
	set<int>::iterator left, right;//定义迭代器
	left = --s.lower_bound(x);
	right = s.lower_bound(x);
	if (x - *left <= *right - x && *left != -MAX_INT)
	{
		ans += x - *left;
		s.erase(left);
	} else {
		ans += *right - x;
		s.erase(right);
	}
	ans %= 1000000;
}

int main()
{
	scanf("%d", &n);
	int hod;
	s.insert(-MAX_INT), s.insert(MAX_INT); //通过插入最大整型和最小整型来防止查找溢出，这是一位大佬的方法，非常秒！！
	for (int i = 1; i <= n; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		if (s.size() == 2)
		{
			hod = a;
			s.insert(b);
		} else 
			if (a == hod) 
				s.insert(b); else find(b);
	}
	printf("%d\n", ans);
	return 0;
}

完事儿~
考虑在写一个关于STL的整合，这一切都要从一只🦇说起……

-------------本文结束,感谢您的阅读-------------