Andrew Stankevich Contests #2

传送门：http://codeforces.com/blog/entry/7770

C - Hyperhuffman

哈夫曼编码题目，注意细节。

 1 #include <cstdio>
 2 #include <queue>
 3 using namespace std;
 4 
 5 typedef long long LL;
 6 #define NN        500007
 7 
 8 struct node {
 9     LL cnt;
10     node *l, *r;
11 }n[NN*2];
12 
13 int p;
14 
15 class cmp {
16 public:
17     int operator() (const node *a, const node *b) {
18         return a->cnt > b->cnt;        // 小顶堆
19     }
20 };
21 
22 LL ddd = 0;
23 
24 LL dfs(node *r)
25 {
26     if (r->l == NULL) return r->cnt * ddd;
27     ++ddd;
28     LL ans = dfs(r->l);
29     ans += dfs(r->r);
30     --ddd;
31     return ans;
32 }
33 
34 priority_queue <node *, vector<node *>, cmp> q;
35 
36 int main(void)
37 {
38     int N;
39     scanf("%d", &N);
40 
41     for(p=0; p<N; ++p) {
42         scanf("%lld", &n[p].cnt);
43         n[p].l = n[p].r = NULL;
44         q.push(&n[p]);
45     }
46     if (q.size() > 1) {
47         do {
48             n[p].l = q.top(); q.pop();
49             n[p].r = q.top(); q.pop();
50             n[p].cnt = n[p].l->cnt + n[p].r->cnt;
51             q.push(&n[p++]);
52         }while(q.size() > 1);
53         printf("%lld
", dfs(q.top()));
54     } else printf("%lld
", q.top()->cnt);
55     return 0;
56 }

View Code

G - Robbers

贪心，使用优先队列优化。

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <queue>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 struct gangster {
 8     int i, k;
 9     double xy;
10     double ans;
11     gangster(){}
12     gangster(int &i, double xy, double ans):i(i), xy(xy), ans(ans), k(0) {}
13 }_g[1000];
14 
15 int operator < (const gangster &a, const gangster &b)
16 {
17     return a.ans < b.ans;
18 }
19 
20 int cmp (const gangster &a, const gangster &b)
21 {
22     return a.i < b.i;
23 }
24 
25 priority_queue <gangster> g;
26 
27 int main(void)
28 {
29     int N, M, Y;
30     scanf("%d%d%d", &N, &M, &Y);
31     for(int i=0; i<N; ++i) {
32         int x;
33         scanf("%d", &x);
34         g.push(gangster(i, ((double)x)/Y, ((double)x)/Y));
35     }
36     for(int i=0; i<M; ++i) {
37         gangster g0 = g.top();
38         g.pop();
39         g0.ans = g0.xy - ((double)++g0.k)/M;
40         g.push(g0);
41     }
42 
43     for(int i=0; !g.empty(); ++i) {
44         _g[i] = g.top();
45         g.pop();
46     }
47     sort(_g, _g + N, cmp);
48     for(int i=0; i<N; ++i) {
49         if (i) putchar(' ');
50         printf("%d", _g[i].k);
51     }
52     return 0;
53 }

View Code