`
mobileliker
  • 浏览: 8158 次
最近访客 更多访客>>
社区版块
存档分类
最新评论

grids 1833 排列

阅读更多
  • 题意

  • 中文不解释
  • 思路

  •     首先看到题目第一个的想法就是全排列,求出提供的全排列一组数据的位置,在找出第K个位置,想起第K最小元,也可以利用快排实现。一想似乎是可行办法。
    但这样就要做两件事:第一,解决如何求全排列;第二,解决如何求提供的一组数据的位置。全排列可以使用分治递归的方法。而求一组数据的位置就较为麻烦,也想到了一个递归的方法,但比较麻烦。因此不行。
        因此查阅了相关的书籍,发现这是一道模拟题。其中n为1024,很大,使用递归不合理。而k<=36,较小,因此可以使用直接求下一个排列数的方法,直接求出结果。
        接下来就是怎么求下一个排列为2 1 4 7 6 5 3(例子来自在线评测那本书),基本的思路是从右往左找出一个数,比后面的至少一个数小,这样的话可以交换实现数变大。例子中即为4可以与后面的比它大的数交换。要使数最小,则选择后面的数最小的一个(当然前提是大于4),即为5,然后进行交换,变为 2 1 5 7 6 4 3。然后很容易想到的就是7 6 4 3要变成最小,书里面的方法是排序,但我发现剩下的内容直接就是逆序了,因此只要进行一次逆序操作就行了,可以节省时间,有O(nlogn)变成O(n)节省了时间。
  • 总结

  • 暂无
  • 代码

  • I 使用直接求下一个+逆序
    (1)C

    #include "stdio.h"
    #include "stdlib.h"
    #define MAX 1024
    int a[MAX+2];
    int main()
    {
        int i,j,m,n,k;
        int tmpi,min;
        int flag;
        scanf("%d",&m);
        while(m--)
        {
            scanf("%d%d",&n,&k);
            for(i=0;i<n;i++) {scanf("%d",&a[i]);}
            while(k--)
            {
                for(i=(n-1)-1;i>=0;i--)
                {
                    if(a[i]<a[i+1])//存在
                    {
                        min = a[i+1];
                        tmpi = i+1;
                        for(j=i+2;j<n;j++)
                        {
                            if(a[j] > a[i] && a[j] < min) {min=a[j];tmpi = j;}
                        }
                        //swap
                        a[tmpi] = a[i];
                        a[i] = min;
                        break;
                    } 
                }
                if(i<0)//最大 
                {
                    for(i=0;i<n;i++) a[i] = i+1; 
                }
                else
                {
                    /*//冒泡排序
                    while(++i<n)
                    {
                        flag = 0;
                        for(j=n-1;j>i;j--)
                        {
                            if(a[j-1]>a[j]){tmpi=a[j-1];a[j-1]=a[j];a[j]=tmpi;flag=1;}
                        }
                        if(flag==0){break;}
                    }*/
                    //逆序
                    j = ++i;
                    while(j<=(n-1+i)/2)
                    {
                        tmpi = a[j];
                        a[j] = a[(n-1) - (j-i)];
                        a[(n-1) - (j-i)] = tmpi;
                        j++;
                    }
                }
                    
            }
            printf("%d",a[0]);
            for(i=1;i<n;i++) printf(" %d",a[i]);
            putchar('\n');
        }
        //system("pause");
        return 0;
    }
    
    
    


    分享到:
    评论

    相关推荐

      Photoshop grids

      网格系统能够帮助设计师精确地排列元素,确保设计的对齐和比例协调,从而达到专业且一致的视觉效果。对于创建响应式网站布局、DIV+CSS以及HTML5的实现,Photoshop网格系统的应用显得尤为关键。 首先,让我们深入...

      poj.grids.cn题型分类

      漂亮的打印问题通常涉及字符串的分割和排列,要求分割后的字符串满足一定的美观度。可以通过动态规划定义状态`dp[i]`表示处理到第`i`个字符时的最优解来进行解决。 以上总结了poj.grids.cn网站中列出的一些常见问题...

      TMS IntraWeb Grids.pdf

      ### TMS IntraWeb Grids – 开发者指南概览 #### TTIWAdvWebGrid与TTIWDBAdvWebGrid组件介绍 在本篇文档中,我们将深入探讨TMS Software提供的TTIWAdvWebGrid和TTIWDBAdvWebGrid组件。这两个组件均作为VCL(Visual ...

      csswizardry-grids, 简单流畅可以嵌套灵活基于Sass的网格系统.zip

      csswizardry-grids, 简单流畅可以嵌套灵活基于Sass的网格系统 csswizardry网格简单。流体。可以嵌套。灵活。基于sass的网格系统。 完全响应移动优先无穷可以嵌套可逆/可以重新排列带/无檐沟无限可能的组合易于理解,...

      S60_Platform_Avkon_UI_Resources_Grids

      Grid 控件的基本结构是由一系列的单元格(cell)组成的,这些单元格按照一定的排列顺序组成网格布局。每个单元格都可以包含文本、图像等元素,并可以通过设置属性来改变外观和行为。 - **Cell 结构**:每个单元格都...

      矩阵排列HTML网页模板是一款插画风格的HTML响应网站模板。_html网站模板_网页源码移动端前端_H5模板_自适应.rar

      矩阵排列HTML网页模板采用了灵活的布局策略,如媒体查询(Media Queries)和流式布局(Fluid Grids),确保页面在手机、平板电脑和桌面电脑上都能呈现出最佳的视觉效果。这样的设计使得网站无需针对每个设备单独开发...

      css-grids-flexbox

      - `flex-direction`属性定义主轴方向(行或列),影响元素的排列顺序。 - `justify-content`和`align-items`分别用于沿主轴和交叉轴对齐元素。 - `flex-wrap`控制元素是否换行,可实现单行或多行布局。 - `flex-...

      ember-quick-grids

      重新排列列 显示/隐藏列 允许数据排序动作 允许分页动作 依存关系 灰烬2.x 灰烬数据2.x jQuery 2.x jQuery UI 1.11.x 安装 ember init hostApp cd hostApp ember install ember-quick-grids 跑步 ember server ...

      kivy-hexagonal-grids:Kivy 六边形网格

      在“kivy-hexagonal-grids”项目中,开发者可能创建了一个自定义的HexagonalGrid类,继承自Kivy的Widget或Layout类,然后重写了布局更新和绘图方法,以在屏幕上绘制出六边形的形状和排列。 **文件名称列表解析** "*...

      angular-grids:角度数据表和ui-grid示例

      **Angular Grids:掌握角度数据表与UI-Grid** Angular Grids是一种强大的工具,用于在Angular应用程序中展示和管理大量数据。在这个特定的项目“angular-grids”中,重点是利用Angular框架结合UI-Grid库来创建高效...

      jQuery响应式自适应浏览器窗口大小图片排列代码.zip

      这主要依赖于媒体查询(Media Queries)、流式布局(Fluid Grids)和灵活的图片(Flexible Images)这三个关键要素。 在这个jQuery插件中,它会监听浏览器窗口的大小变化,当窗口大小发生变化时,会动态调整图片的...

      CasedClosed-project-using-grids:一个使用网格的简单项目网站

      描述中的“封闭式项目”可能指的是该项目设计时对元素的排列和布局有特定的规则和结构,而“使用网格”则意味着它利用了CSS Grid布局来实现这一点。 **HTML (HyperText Markup Language)** HTML是网页内容的基础,...

      css-grids

      Grid容器是包含Grid布局的所有元素,而Grid项目则是容器内的子元素,它们会按照Grid规则进行排列。 **定义Grid轨道** 使用`grid-template-columns`和`grid-template-rows`属性来定义Grid的行和列。这些属性可以接受...

      frontend-store-learning-grids-curso

      在"frontend-store-learning-grids-curso-main"目录下,我们可以期待找到一系列与创建这种网格布局相关的文件和资源。 首先,HTML5引入了新的 semantic elements(语义元素),如, , , , , , 和,这些元素有助于...

      extra-strength-responsive-grids:用于响应式Web设计的Fluid CSS网格系统用于响应式Web设计的Fluid CSS网格系统。 完全控制您的布局

      列在行内排列,可以根据屏幕宽度变化进行堆叠或并排显示。系统通常包含多个预定义的断点,这些断点定义了不同屏幕尺寸下的列数和间距。例如,开发者可以设定在大屏幕设备上显示4列,在平板电脑上显示2列,在手机上...

      破译网格设计

      网格设计是一种在平面设计、网页设计和用户界面设计中广泛使用的技术,它是一种将设计元素按照一定的规则排列组合的方法。通过使用网格,设计师可以为各种视觉元素创建一致的结构,使布局更加有组织和易于导航。这种...

      jQuery响应浏览器窗口大小图片排列代码

      响应式设计的核心在于媒体查询(Media Queries)和流式布局(Fluid Grids),但jQuery可以作为辅助工具,用于实现更精细的交互效果。在这个图片画廊中,jQuery可能首先计算出容器的宽度,然后根据这个宽度调整图片的...

      jquery div格子拖动排列效果特效代码

      1. **选择元素**:使用jQuery的选择器选取需要实现拖动功能的div元素,例如 `$("#grids .grid")` 可以选取所有类名为`grid`的子元素。 2. **绑定事件**:使用`.on()`方法为这些元素绑定鼠标事件,如`mousedown`...

    Global site tag (gtag.js) - Google Analytics