poj 2418 Hardwood Species(2分）

poj 2418 Hardwood Species(二分）

poj 2418 - Hardwood Species

题目大意：给出一系列字符串，统计每个字符串出现的概率（保留4位小数）。

解题思路：一开始看到时间10s，觉得是水题，就很嘚瑟用暴力去做，结果超时了，后来觉得数据可能比较大，想到二叉树，不过觉得用二分貌似也可以，就试着做了了一下。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 10005;
const int M = 40;

struct tree {
	char name[M];
	int cnt;
	tree() {
		memset(name, 0, sizeof(name));
		cnt = 0;
	}
}t[N];
int n = 0, sum = 0;

bool cmp(const tree& a, const tree& b) {
	return strcmp(a.name, b.name) < 0;
}

bool search(char tmp[]) {
	int l = 0, r = n;
	if (strcmp(t[0].name, tmp) == 0)  {
		t[0].cnt++;
		return true;
	}
	while (1) {
		int mid = (l + r) / 2;
		if (l >= r - 1) return false;
		
		if (strcmp(t[mid].name, tmp) < 0)
			l = mid;
		else if (strcmp(t[mid].name, tmp) > 0)
			r = mid;
		else {
			t[mid].cnt++;
			return true;
		}
	}
	return false;
}

int main () {
	char tmp[M];
	while (gets(tmp)) {
		if(tmp[0] == '\0') break;
		sum++;
		if (!search(tmp)) {
			strcpy(t[n].name, tmp);
			t[n].cnt++;
			n++;
			sort(t, t + n, cmp);
		}
	}

	for (int i = 0; i < n; i++)
		printf("%s %.4lf\n", t[i].name, (t[i].cnt * 100.0) / sum);
	return 0;
}