原题链接：http://poj.org/problem?id=2153
简单题，map，平衡树均可。。
map：
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<string> 6 #include<map> 7 using std::cin; 8 using std::map; 9 using std::string; 10 map<string, int> ret; 11 int main() { 12 #ifdef LOCAL 13 freopen("in.txt", "r", stdin); 14 freopen("out.txt", "w+", stdout); 15 #endif 16 string buf; 17 int n, m, v, tmp; 18 while (cin >> n) { 19 getchar(); 20 for (int i = 0; i < n; i++) { 21 getline(cin, buf); 22 ret[buf] = 0; 23 } 24 cin >> m; 25 while (m--) { 26 int ans = 0; 27 for (int i = 0; i < n; i++) { 28 cin >> v; 29 getchar(); 30 getline(cin, buf); 31 ret[buf] += v; 32 } 33 tmp = ret["Li Ming"]; 34 map<string, int>::iterator ite; 35 for (ite = ret.begin(); ite != ret.end(); ++ite) { 36 if (ite->second > tmp) ans++; 37 } 38 printf("%d ", ans + 1); 39 } 40 ret.clear(); 41 } 42 return 0; 43 }
平衡树：
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cstdio> 6 typedef char State[35]; 7 char *target = "Li Ming"; 8 const int Max_N = 11000; 9 struct Node { 10 State name; 11 int data, s; 12 bool color; 13 Node *fa, *ch[2]; 14 inline void set(int _v, char *src, bool _color, int i, Node *p) { 15 data = _v, color = _color, s = i; 16 fa = ch[0] = ch[1] = p; 17 strcpy(name, src); 18 } 19 inline void push_up() { 20 s = ch[0]->s + ch[1]->s + 1; 21 } 22 inline int cmp(char *src) const { 23 if (0 == strcmp(src, name)) return -1; 24 else if (-1 == strcmp(src, name)) return 0; 25 return 1; 26 } 27 }; 28 struct RedBlackTree { 29 Node *root, *null; 30 Node stack[Max_N], *tail; 31 void init() { 32 tail = &stack[0]; 33 null = tail++; 34 null->set(0, "", 0, 0, NULL); 35 root = null; 36 } 37 inline Node *newNode(char *name, int v) { 38 Node *p = tail++; 39 p->set(v, name, 1, 1, null); 40 return p; 41 } 42 inline void rotate(Node* &x, bool d) { 43 Node *y = x->ch[!d]; 44 x->ch[!d] = y->ch[d]; 45 if (y->ch[d] != null) y->ch[d]->fa = x; 46 y->fa = x->fa; 47 if (x->fa == null) root = y; 48 else x->fa->ch[x->fa->ch[0] != x] = y; 49 y->ch[d] = x; 50 x->fa = y; 51 y->s = x->s; 52 x->push_up(); 53 } 54 inline void insert(char *name, int v = 0) { 55 int d = 0; 56 Node *x = root, *y = null; 57 while (x->s) { 58 x->s++; 59 d = x->cmp(name); 60 y = x, x = x->ch[d]; 61 } 62 x = newNode(name, v); 63 if (y != null) { d = x->cmp(y->name), y->ch[!d] = x; } 64 else root = x; 65 x->fa = y; 66 insert_fix(x); 67 } 68 inline void insert_fix(Node* &x) { 69 while (x->fa->color){ 70 Node *par = x->fa, *Gp = par->fa; 71 bool d = par == Gp->ch[0]; 72 Node *uncle = Gp->ch[d]; 73 if (uncle->color) { 74 par->color = uncle->color = 0; 75 Gp->color = 1; 76 x = Gp; 77 } else if (x == par->ch[d]) { 78 rotate(x = par, !d); 79 } else { 80 Gp->color = 1; 81 par->color = 0; 82 rotate(Gp, d); 83 } 84 } 85 root->color = 0; 86 } 87 inline Node *find(Node *x, char *name) { 88 while (x->s) { 89 int d = x->cmp(name); 90 if (-1 == d) break; 91 x = x->ch[d]; 92 } 93 return x; 94 } 95 inline void Modify(char *str, int v) { 96 Node* ret = find(root, str); 97 ret->data += v; 98 } 99 inline void dfs(Node *x, int v, int &ans) { 100 if (x != null){ 101 dfs(x->ch[0], v, ans); 102 if (x->data > v) ans++; 103 dfs(x->ch[1], v, ans); 104 } 105 } 106 inline void query() { 107 int cnt = 0, ans = 0; 108 int v = find(root, target)->data; 109 dfs(root, v, ans); 110 printf("%d ", ans + 1); 111 } 112 }rbt; 113 int main(){ 114 #ifdef LOCAL 115 freopen("in.txt", "r", stdin); 116 freopen("out.txt", "w+", stdout); 117 #endif 118 char buf[100]; 119 int n, m, val; 120 while (~scanf("%d ", &n)) { 121 rbt.init(); 122 for (int i = 0; i < n; i++) { 123 gets(buf); 124 rbt.insert(buf); 125 } 126 scanf("%d ", &m); 127 while (m--) { 128 for (int i = 0; i < n; i++) { 129 gets(buf); 130 sscanf(buf, "%d", &val); 131 rbt.Modify(strchr(buf, ' ') + 1, val); 132 } 133 rbt.query(); 134 } 135 } 136 return 0; 137 }