原题链接：
简单题。。
平衡树，写了个模板。。动态分配内存确实很慢。。。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using std::string; 8 template 9 class sb_tree{ 10 private: 11 struct Node{ 12 T data; 13 int s, c; 14 Node *ch[2]; 15 Node(const T&d) :s(1), c(1), data(d){} 16 Node() :s(0), c(0){ ch[0] = ch[1] = this; } 17 inline void push_up(){ 18 s = ch[0]->s + ch[1]->s + c; 19 } 20 inline int cmp(const T&v) const{ 21 return v == data ? -1 : v > data; 22 } 23 }*null, *root; 24 inline void rotate(Node* &x, int d){ 25 Node *k = x->ch[!d]; 26 x->ch[!d] = k->ch[d]; 27 k->ch[d] = x; 28 k->s = x->s; 29 x->push_up(); 30 x = k; 31 } 32 inline void Maintain(Node* &x, int d){ 33 if (x->ch[d] == null) return; 34 if (x->ch[d]->ch[d]->s > x->ch[!d]->s){ 35 rotate(x, !d); 36 } else if (x->ch[d]->ch[!d]->s > x->ch[!d]->s){ 37 rotate(x->ch[d], d), rotate(x, !d); 38 } else { 39 return; 40 } 41 Maintain(x, 0), Maintain(x, 1); 42 } 43 inline void insert(Node *&x, const T&data){ 44 if (!x->s){ 45 x = new Node(data); 46 x->ch[0] = x->ch[1] = null; 47 } else{ 48 x->s++; 49 int d = x->cmp(data); 50 if (-1 == d){ 51 x->c++; 52 return; 53 } 54 insert(x->ch[d], data); 55 x->push_up(); 56 Maintain(x, d); 57 } 58 } 59 inline void del(Node *&x, const T&data){ 60 if (!x->s) return ; 61 x->s--; 62 int d = x->cmp(data); 63 if (-1 == d){ 64 if (x->c > 1){ 65 x->c--; 66 return; 67 } else if (!x->ch[0]->s || !x->ch[1]->s){ 68 x = x->ch[0]->s ? x->ch[0] : x->ch[1]; 69 } else { 70 Node *ret = x->ch[1]; 71 for (; ret->ch[0]->s; ret = ret->ch[0]); 72 del(x->ch[1], x->data = ret->data); 73 } 74 } else { 75 del(x->ch[d], data); 76 } 77 if (x->s) x->push_up(); 78 } 79 void clear(Node* &x){ 80 if (x->s) clear(x->ch[0]), clear(x->ch[1]), delete x; 81 } 82 public: 83 sb_tree() :null(new Node), root(null){} 84 ~sb_tree(){ clear(root), delete null; } 85 inline void clear(){ clear(root), root = null; } 86 inline void insert(const T&data){ 87 insert(root, data); 88 } 89 inline void del(const T&data){ 90 del(root, data); 91 } 92 inline bool find(const T&data){ 93 Node *x = root; 94 while (x->s && x->data != data) x = x->ch[x->data < data]; 95 return x->s; 96 } 97 inline const T&kth(int k){ 98 Node *x = root; 99 for (int t = 0; x != null;){100 t = x->ch[0]->s;101 if (k <= t) x = x->ch[0];102 else if (t + 1 <= k && k <= t + x->c) break;103 else k -= t + x->c, x = x->ch[1];104 }105 return x->data;106 }107 inline int rank(const T&data){108 Node *x = root;109 int t = 0, cur = 0;110 for (cur = 0; x != null;){111 t = x->ch[0]->s;112 if (data == x->data) break;113 else if (data < x->data) x = x->ch[0];114 else cur += t + x->c, x = x->ch[1];115 }116 return cur + t + 1;117 }118 inline const T&operator[](int k){119 return kth(k);120 }121 inline const T&preorder(const T&data){122 Node *x = root, *y = 0;123 while (x->s){124 if (x->data < data) y = x, x = x->ch[1];125 else x = x->ch[0];126 }127 return y ? y->data : data;128 }129 inline const T&successor(const T&data){130 Node *x = root, *y = 0;131 while (x->s){132 if (data < x->data) y = x, x = x->ch[0];133 else x = x->ch[1];134 }135 return y ? y->data : data;136 }137 inline int size(){ return root->s; }138 inline void query(Node *x, int cnt){139 if (x != null){140 query(x->ch[0], cnt);141 string str = x->data;142 printf("%s %.4lf\n", str.c_str(), (double)x->c * 100 / cnt);143 query(x->ch[1], cnt);144 }145 }146 inline void query(){147 int cnt = size();148 query(root, cnt);149 }150 };151 int main(){152 #ifdef LOCAL153 freopen("in.txt", "r", stdin);154 freopen("out.txt", "w+", stdout);155 #endif156 char buf[100];157 sb_tree ans;158 while (gets(buf)) ans.insert(buf);159 ans.query();160 return 0;161 }
如果不想写平衡树，就写个快排吧。。注意用c提交：
1 #include2 #include 3 #include 4 typedef char State[33]; 5 State st[1000010]; 6 int cmp(const char* src, const char *_src){ 7 return strcmp((char *)src, (char *)_src); 8 } 9 int main(){10 State ret, buf;11 int i, k, cnt = 0;12 while (gets(ret)) strcpy(st[cnt++], ret);13 qsort(st, cnt, sizeof(st[0]), cmp);14 i = 0;15 while (i < cnt){16 strcpy(buf, st[i]), k = 0;17 for (; 0 == strcmp(buf, st[i]); i++) k++;18 printf("%s %.4lf\n", buf, (double)k * 100 / cnt);19 }20 return 0;21 }