蟻本,データ構造

ヒープ実装

```
int heap[1000], sz = 0;
void push(int x) {
	int i = sz++;
	while (i > 0) {
		int p = (i - 1) / 2;
		if (heap[p] <= x)break;
		heap[i] = heap[p];
		i = p;
	}
	heap[i] = x;
}
int pop() {
	int ret = heap[0];
	int x = heap[--sz];
	int i = 0;
	while (i * 2 + 1 < sz) {
		int a = i * 2 + 1, b = i * 2 + 2;
		if (b < sz&&heap[b] < heap[a])a = b;
		if (heap[a] >= x)break;
		heap[i] = heap[a];
		i = a;
	}
	heap[i] = x;
	return ret;
}
```
キューの簡単な使用例

```
#include<iostream>
#include<queue>
using namespace std;

int main() {
	priority_queue<int>pque;
	pque.push(3);
	pque.push(5);
	pque.push(1);
	while (!pque.empty()) {
		cout << pque.top();
		pque.pop();
	}
	return 0;
}
```
キューを用いる問題
トラックで距離Lの道を移動します。はじめトラックにはガソリンがP積まれています。このトラックは距離1走るとガソリンが１消費されます。途中でガソリンが０になってしまうとトラックは停止してしまい、移動に失敗してしまう。途中にはN個ガソリンスタンドがあります。各ガソリンスタンドiは道のスタート地点から距離Aiの地点にあって、Biだけガソリンを補給することができます。トラックの燃料タンクの容量に制限はなく、いくらでもガソリンを補給することができます。トラックは移動を完了できるでしょうか？またその際、最小で何回のガソリンの補給が必要でしょうか？完了できる場合は最小の補給回数を、できない場合は-1を出力してください。

・ガソリンスタンドiを通過した際に、プライオリティーキューにBiを追加する。
・燃料タンクが空になったとき、
プライオリティーキューが空であれば、移動は達成できない
プライオリティーキューから最も大きい数字を取り出し、そこでガソリンを補給したことにする

```
#include<iostream>
#include<queue>
using namespace std;
int L, P, N;
int A[10010], B[10010];
int main() {
	cin >> L >> P >> N;
	for (int i = 0; i < N; ++i)cin >> A[i] >> B[i];
	//簡単のためゴールをガソリンスタンドに追加
	A[N] = L;
	B[N] = 0;
	N++;
	//ガソリンスタンドを管理する順位キュー
	priority_queue<int>que;
	//ans:補給回数 pos:今いる場所 tank:タンクのガソリンの量
	int ans = 0,pos = 0,tank = P;
	for (int i = 0; i < N; ++i) {
		//次に進む距離
		int d = A[i] - pos;
		//十分な量になるまでガソリンを補給
		while (tank - d < 0) {
			if (que.empty()) {
				puts("-1");
				return 0;
			}
			tank += que.top();
			que.pop();
			ans++;
		}
		tank -= d;
		pos = A[i];
		que.push(B[i]);
	}
	cout << ans;
	return 0;
}
```
Fence Repair
農夫ジョンは、フェンスを修理するため、とても長い板からＮ個の板を切り出そうとしています。切り出そうとしている板の長さはL1,L2,,,,LNであり、元の板の長さはちょうどこれの合計になっています。板を切断する際には、その板の長さの分だけのコストがかかります。例えば、長さ２１の板から長さ5,8,8の３つの板を切り出したいとします。長さ２１の板を長さ１３と８の板に切断すると、コストが２１かかります。その１３の板をさらに５と８の板に切断すると、コストが１３かかります。合計で３４のコストがかかります。最小で、どれだけのコストですべての板を切り出すことができるでしょうか？

これをキューを用いて解きたい。

二分探索木
実装はめんどくさいからいいや
簡単な実用例
setは集合を二分探索木で管理するコンテナで、mapはキーとそれに対応する値を管理するコンテナ。
例

```
#include<iostream>
#include<set>
using namespace std;

int main() {
	set<int>s;
	//要素の追加
	s.insert(1);
	s.insert(3);
	s.insert(5);
	//要素の検索
	set<int>::iterator ite;;
	ite = s.find(1);
	if (ite == s.end())cout<<"not found";
	else cout << "found";

	ite = s.find(2);
	if (ite == s.end())cout<<"not found";
	else cout << "found";

	s.erase(3);

	if (s.count(3) != 0)cout << "found";
	else cout << "not found";

	for (ite = s.begin(); ite != s.end(); ++ite) {
		cout << *ite;
	}
	return 0;
}
```

union-find木の実装、はまた今度で

union-find木を使う問題
N匹の動物がいて、1,2,,,,Nと番号が付けられています。動物は全て３つの種類A,B,Cのいずれかです。AはBを食べ、BはCを食べ、CはAを食べます。次の2種類の情報が順番にk個与えられます。
・タイプ1：ｘとyは同じ種類です。
・タイプ2:xはyを食べます。
これらはすべて正しいとは限りません。以前に与えられた情報と矛盾する情報や、x,yが正しい番号(1,2,,,,N)でないような正しくない情報が与えられる可能性があります。K個の情報のうち、そのような情報の個数を出力してください。そのような情報は捨てると考えます。
・1<=N<=50000
・0<=K<=100000

効率的に情報を管理したい。各動物iについて、3つの要素i-A,i-B,i-Cを作り、３＊N個の要素でのunion-findを作ります。このunion-findを、次のようなものと考えます。
・i-xは「iが種類xである場合」を表す。
・各グループは、それらがすべて同時に起こることがわかっていることを表す。

例えば、i-Aとj-Bが同じグループである場合、iが種類Aならばjは必ず種類Bであり、jが種類Bならばiは必ず種類Aであることを表しています。すると各情報について、以下を行えばよいことがわかる
・タイプ１、:xとyが同じ種類....「x-Aとy-A」「ｘ-Bとy-B」「x-Cとy-C」の3つのペアを併合
・タイプ２、:xはyを食べる....「x-Aとy-B」「x-Bとy-C」「x-Cとy-A」の3つのペアを併合
ただしそれぞれの前に、矛盾が起きているかのチェックをします。例えばタイプ1の場合、x-Aとy-Bまたはy-Cが同じグループでないか等をチェックします。