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