Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

达人来看看我这代码问题出在哪儿了?或者给一些强悍的测试实例。谢谢

Posted by lisanwan at 2008-11-30 09:52:31 on Problem 1521
#include <iostream>
#include <string>
#include <map>
#include <iomanip>
using namespace std;
//////////////////////////////////////////////////////////////////////////
void siftdown(int v[], int i, int n)
{
	int temp = v[i];
	while(2*i <= n)
	{
		int child = 2*i;
		if(child < n && v[child+1] < v[child])
			child++;
		if(v[child] >= temp)
			break;
		v[i] = v[child];
		i = child;
	}
	v[i] = temp;
}
//////////////////////////////////////////////////////////////////////////
int heap_delete(int v[], int &n)
{
	int val = v[1];
	v[1] = v[n];
	n--;
	siftdown(v, 1, n);
	return val;
}
//////////////////////////////////////////////////////////////////////////
void heap_insert(int val, int v[], int& n)
{
	n++;
	int i = n;
	while(i > 1 && val < v[i/2])
	{
		v[i] = v[i/2];
		i /= 2;
	}
	v[i] = val;
}
//////////////////////////////////////////////////////////////////////////
void heapify(int v[], int n)
{
	for(int i = n/2; i >= 1; i--)
		siftdown(v, i, n);
}
//////////////////////////////////////////////////////////////////////////
int main()
{
	while(1)
	{	
		string s;
		getline(cin, s, '\n');
		if(!s.compare("END"))
			break;
		map<char, int> char_count;
		for(string::size_type i = 0; i != s.size(); i++)
			++char_count[s[i]];
		int i = 1;
		int v[50] = {0};
		int num = 0;
		for(map<char, int>::const_iterator map_it = char_count.begin();
			map_it != char_count.end();
			map_it++)
		{
			v[i++] = map_it->second;
			num += map_it->second;
		}
		int size = i-1;
		if(size == 1)
		{
			cout<<"8 1 8"<<endl;
			continue;
		}
		int sum = 0;
		int n = size;
		heapify(v, size);
		for(i = 1; i <= n-1; i++)
		{
			int l, r;
			l = heap_delete(v, size);
			r = heap_delete(v, size);
			int lr = l + r;
			sum += lr;
			heap_insert(lr, v, size);
		}
		cout<<num*8<<" "
			<<sum<<" "
			<<fixed<<setprecision(1)<<((double)num*8)/sum<<endl;
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator