Codeforces 977D 题解报告

￡神魔★判官ぃ 2022-05-25 05:00 315阅读 0赞

一、题目

http://codeforces.com/contest/977/problem/D

二、分析

依题意，可以考虑一个数是3的多少次幂，可以有余数。
比如18是3的2次幂，余数为2；
9是3的2次幂，余数为0；
2是3的0次幂，余数为2。

首先要把幂从高到低的顺序排列，比如9（3的2次幂）必然排在3（3的1次幂）的前面。
对于同一次幂，要按从小到大的顺序排序，这样后面的数必然为前面的数的2倍。比如9和18都是3的2次幂。这样18就得排在9的后面。

数据结构可以使用vector

三、程序

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. typedef long long LL;
  6. int count3(LL x)
  7. {
  8.     int ret = 0;
  9.     while(x % 3 == 0)
  10.     {
  11.         ret++;
  12.         x /= 3;
  13.     }
  15.     return ret;
  16. }
  18. int main()
  19. {
  20.     int n;
  21.     cin >> n;
  23.     vector<pair<int, LL>> v(n);
  24.     for(int i = 0; i < n; i++)
  25.     {
  26.         cin >> v[i].second;
  27.         v[i].first = -count3(v[i].second);
  28.     }
  30.     sort(v.begin(), v.end());
  32.     for(int i = 0; i < n; i++)
  33.     {
  34.         printf("%I64d%c", v[i].second, " \n"[i + 1 == n]);
  35.     }
  36. }

TopCoder & Codeforces & AtCoder交流QQ群：648202993
更多内容请关注微信公众号
wechat\_public\_header.jpg

发表评论

表情：
评论列表 （有 0 条评论，315人围观）

还没有评论，来说两句吧...

相关阅读