原 初学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 条评论
登录 后参与评论

相关文章

来自专栏光变

Spring PlaceHolder使用注意事项

对Spring Property Placeholder如何使用,以及使用过程中遇到的问题做了简单的描述。

1111
来自专栏Hongten

FreeMarker_模板引擎_代码自动生成器_源码下载

你可以到freemarker的官网上去,那里有很详细的介绍:http://freemarker.org/

2631
来自专栏pangguoming

IntPtr 转 string

假设有 intPtr pBuffer 方法一: 直接使用Marshal.PtrToStringAnsi方法: string ss = Marshal.PtrTo...

36914
来自专栏Java帮帮-微信公众号-技术文章全总结

JSP与EL表达式重点学习笔记(1)

Jsp&el表达式 JSP指令 ? JSP指令概述 JSP指令的格式:<%@指令名 attr1=”” attr2=”” %>,一般都会把JSP指令放到JSP文件...

3789
来自专栏吴伟祥

Spring 条件注解 @Conditional

Spring 4提供了一个更通用的基于条件的Bean的创建方式,即使用@Conditional注解。

1503
来自专栏一个会写诗的程序员的博客

《Groovy极简教程》第1章 Groovy简介《Groovy极简教程》第1章 Groovy简介参考资料

官网文档:http://www.groovy-lang.org/documentation.html Github源码:https://github.com/...

852
来自专栏Jed的技术阶梯

Kafka 中使用 Avro 序列化框架(二):使用 Twitter 的 Bijection 类库实现 avro 的序列化与反序列化

使用传统的 avro API 自定义序列化类和反序列化类比较麻烦,需要根据 schema 生成实体类,需要调用 avro 的 API 实现 对象到 byte[]...

3054
来自专栏IT可乐

SpringMVC详解(五)------参数绑定

  参数绑定,简单来说就是客户端发送请求,而请求中包含一些数据,那么这些数据怎么到达 Controller ?这在实际项目开发中也是用到的最多的,那么 Spri...

32810
来自专栏javathings

Spring Boot 中,表单数据传值方式

之前总结过 Spring Boot 前端页面传 Json 数据至 Controller 的例子。《spring-boot 中,json 数据传值方式》

7232
来自专栏从流域到海域

Java Beans

JavaBeans事实上有三层含义。首先,JavaBeans是一种规范,一种在Java(包括JSP)中使用可重复使用的Java组件的技术规范,也可以说成我们常...

1886

扫码关注云+社区

领取腾讯云代金券