Codeforces 977D 题解报告

一、题目

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<pair>,这里power代表x为3的几次幂。因为vector使用sort函数是从小到大排的,咱们这里是根据3的幂从大到小的顺序排,所以具体排序时只要将power取其相反数,就可以达到从大到小排的目的。</pair

三、程序

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int count3(LL x)
{
    int ret = 0;
    while(x % 3 == 0)
    {
        ret++;
        x /= 3;
    }
    return ret;
}
int main()
{
    int n;
    cin >> n;
    vector<pair<int, LL>> v(n);
    for(int i = 0; i < n; i++)
    {
        cin >> v[i].second;
        v[i].first = -count3(v[i].second);
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < n; i++)
    {
        printf("%I64d%c", v[i].second, " \n"[i + 1 == n]);
    }
}

原文发布于微信公众号 - 海天一树(gh_de7b45c40e8b)

原文发表时间:2018-05-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C语言及其他语言

【每日一题】问题 1157: 【亲和数】

古希腊数学家毕达哥拉斯在自然数研究中发现,220的所有真约数(即不是自身的约数)之和为: 1+2+4+5+10+11+20+22+44+55+110=284...

7920
来自专栏xingoo, 一个梦想做发明家的程序员

MFC中注释含义

下面是 CStdioFile 类的部分列表,其中使用了 MFC 在其类中按类成员的用法划分它们时所采用的大多数标准注释: class CStdioFile :...

20570
来自专栏智能大石头

深度解析C++拷贝构造函数

自2003年开始,断断续续用了12年C++,直到这两年做物联网嵌入式开发,感觉对C++的掌握仅有10%左右。 习惯了C#开发,C++倒显得难以下手!今天就一个函...

22690
来自专栏JackeyGao的博客

Leetcode 算法 - 7. Reverse Integer

注意点: 此问题在2014-11-10有更新, 加入了对溢出的控制, 当出现溢出则返回为0. 而Python中没有溢出的行为, 所以为了Accepted, 加入...

7420
来自专栏chafezhou

fire让命令行接口更简单

14650
来自专栏deepcc

javascript 中的 delete

36780
来自专栏刘望舒

设计模式(九)模版方法模式

1.模版方法模式简介 模版方法模式介绍 在软件开发中,有时会遇到类似的情况,某个方法的实现需要多个步骤,其中有些步骤是固定的,而有些步骤并不固定,存在可变性。为...

20760
来自专栏好好学java的技术栈

一文看透java8新特性

毫无疑问,Java 8发行版是自Java 5(发行于2004,已经过了相当一段时间了)以来最具革命性的版本。Java 8 为Java语言、编译器、类库、开发工具...

13820
来自专栏向治洪

Java 8新特性

编者注:Java 8已经公布有一段时间了,种种迹象表明Java 8是一个有重大改变的发行版。 在Java Code Geeks上已经有大量的关于Java 8 的...

39760
来自专栏积累沉淀

【译】Java 8的新特性—终极版

声明:本文翻译自Java 8 Features Tutorial – The ULTIMATE Guide,翻译过程中发现并发编程网已经有同学翻译过了:...

261100

扫码关注云+社区

领取腾讯云代金券