专栏首页海天一树Codeforces 977D 题解报告

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),作者:.

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • AtCoder Beginner Contest 100 完整解题报告

    https://beta.atcoder.jp/contests/abc100/tasks

    海天一树
  • 程序员必须掌握的8大排序算法

    分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基数排序)...

    海天一树
  • AtCoder Beginner Contest 101 完整解题报告

    分析:因为最小的数为1,最终所有的数必然全变为1。计算1左边和右边的数各分为多少段,加起来即可得到结果。 假设1位于第i个位置,则左边的分段为(i - 1) /...

    海天一树
  • 2019河南科技学院发现杯

    来到学校后第一次参加算法比赛,听学长说去年的难度非常高,所以这次比赛目标就是得到分数。但今年的难度整体偏低,第八题做的比较懵,第十题不会做(连题都看不懂 ),其...

    dejavu1zz
  • 1038 统计同成绩学生 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • 挑战程序竞赛系列(95):3.6数值积分(1)

    挑战程序竞赛系列(95):3.6数值积分(1) 传送门:AOJ 1313: Intersection of Two Prisms 题意: 有一个侧棱与Z轴平行...

    用户1147447
  • POJ 刷题系列:3349. Snowflake Snow Snowflakes

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/...

    用户1147447
  • 2017.5.13阶段模拟考试

    预计分数:100+50(其实感觉自己写的对)+100 实际分数:100+0+100 P1149 火柴棒等式 题目描述 给你n根火柴棍,你可以拼出多少个形如“A+...

    attack
  • hdu1040

    @坤的
  • 洛谷P4779 【模板】单源最短路径(标准版)

    前几天写dijkstra的时候没打vis标记居然A了,然后天真的我就以为Dijkstra不用打标记。

    attack

扫码关注云+社区

领取腾讯云代金券