专栏首页聊聊技术原 初学ACM - 组合数学基础题目PKU

原 初学ACM - 组合数学基础题目PKU

题目链接:http://poj.org/problem?id=1833

题意说的很清楚,就是找出当前排列后的第k个排列。

很容易的,就能利用STL的next_permulation()函数写出一个答案:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int data[1025];

int main(){
    int n,k,m;
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d%d",&n,&k);
        for(int i=0; i<n; i++)
        {
            scanf("%d",&data[i]);
        }
        while(k--)
            next_permutation(data,data+n);
        for(int i=0; i<n; i++)
        {
            printf("%d ",data[i]);
        }
        putchar('\n');
    }
    return 0;
}

然而提交上去,会提示超时...

有些摸不着头脑,因为网上AC的代码基本也都是调用k次next_permulation写的。

然后看到了这篇文章:Poj 1833 排列 —— 一道水题的凌乱

才明白,原来多次调用printf函数也会超时。。

于是,就一次把它复制到输出缓冲区吧。

#include <iostream>
#include <cstdio>
#include <iterator>
#include <algorithm>
using namespace std;

int data[1025];

int main()
{
    int n,k,m;
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d%d",&n,&k);
        for(int i=0; i<n; i++)
        {
            scanf("%d",&data[i]);
        }
        while(k--)
            next_permutation(data,data+n);
        copy(data,data+n-1,ostream_iterator<int>(cout," "));
        cout<<data[n-1]<<endl;
    }
    return 0;
}

这时就AC了,只用了500ms,说明调用printf至少消耗了500ms的时间。不过同样的代码,使用C++模式提交就跑了985ms,几乎是压线跑完。。

Run ID User Problem Result Memory Time Language Code Length Submit Time

14813838  Arclabs001 1833 Accepted 696K 500MS G++ 477B 2015-10-14 17:41:22

14813836  Arclabs001 1833 Accepted 204K 985MS C++ 477B 2015-10-14 17:40:55

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 原 初学算法-快速排序与线性时间选择(De

    不高不富不帅的陈政_
  • 原 初学算法-基于最小堆的优先级队列C++

    不高不富不帅的陈政_
  • 原 HDOJ 1002 A + B Pro

    不高不富不帅的陈政_
  • P3366 【模板】最小生成树

    题目描述 如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出orz 输入输出格式 输入格式: 第一行包含两个整数N、M,表示该图共有N个结点和...

    attack
  • 生理周期POJ 1006

    Description 人生来就有三个生理周期,分别为体力、感情和智力周期,它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天,人会...

    attack
  • codevs 4163 hzwer与逆序对

     时间限制: 1 s  空间限制: 256000 KB  题目等级 : 黄金 Gold 题解 题目描述 Description hzwer在研究逆序对。 对于数...

    attack
  • 1074 食物链 2001年NOI全国竞赛

    1074 食物链 2001年NOI全国竞赛 时间限制: 3 s 空间限制: 64000 KB 题目等级 : 钻石 Diamond 题目描述 Des...

    attack
  • 51Nod-1618-树或非树

    ACM模版 描述 ? ? 题解 这是 CFCF 上的一道原题,没有啥思路,于是找来一下题解,找到了一个远古的博客(jasonzhu8’s blog),里面有这个...

    f_zyj
  • Android 圆形ImageView

    饮水思源为名
  • 程序在内存中的分布

    1、对于x86 架构的系统来说,器虚拟空间为4GB. 2、高位的1GB为内核空间。3、低位的3GB由Text segment(ELF)、Data segment...

    Elapse

扫码关注云+社区

领取腾讯云代金券