Poj 2418 Hardwood Species(二分)

poj 2418 - Hardwood Species
一連の文字列を与え、各文字列の出現確率を統計する(4桁の小数を保持する).
最初は时间10 sを见て、水の问题だと思って、とてもごろごろして暴力でやって、结局タイムアウトして、それからデータが比较的に大きいかもしれないと思って、二叉树を思い出して、でも二分でもいいようだと思って、やってみました.

#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
", t[i].name, (t[i].cnt * 100.0) / sum);
	return 0;
}