| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
达人来看看我这代码问题出在哪儿了?或者给一些强悍的测试实例。谢谢#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator