Andrew Stankevich Contests #2-白红宇

Andrew Stankevich Contests #2

阅读量：5018 次

发布时间：2019-06-12

本文共 1842 字，大约阅读时间需要 6 分钟。

传送门：

C - Hyperhuffman

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

1 #include 
      
        2 #include 
       
         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 
        
         , cmp> q;35 36 int main(void)37 {38     int N;39     scanf("%d", &N);40 41     for(p=0; p
         
           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\n", dfs(q.top()));54     } else printf("%lld\n", q.top()->cnt);55     return 0;56 }

View Code

G - Robbers

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

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           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 
          
            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