题意
中文不解释
思路
首先看到题目第一个的想法就是全排列,求出提供的全排列一组数据的位置,在找出第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;
}
分享到:
相关推荐
网格系统能够帮助设计师精确地排列元素,确保设计的对齐和比例协调,从而达到专业且一致的视觉效果。对于创建响应式网站布局、DIV+CSS以及HTML5的实现,Photoshop网格系统的应用显得尤为关键。 首先,让我们深入...
漂亮的打印问题通常涉及字符串的分割和排列,要求分割后的字符串满足一定的美观度。可以通过动态规划定义状态`dp[i]`表示处理到第`i`个字符时的最优解来进行解决。 以上总结了poj.grids.cn网站中列出的一些常见问题...
### TMS IntraWeb Grids – 开发者指南概览 #### TTIWAdvWebGrid与TTIWDBAdvWebGrid组件介绍 在本篇文档中,我们将深入探讨TMS Software提供的TTIWAdvWebGrid和TTIWDBAdvWebGrid组件。这两个组件均作为VCL(Visual ...
csswizardry-grids, 简单流畅可以嵌套灵活基于Sass的网格系统 csswizardry网格简单。流体。可以嵌套。灵活。基于sass的网格系统。 完全响应移动优先无穷可以嵌套可逆/可以重新排列带/无檐沟无限可能的组合易于理解,...
Grid 控件的基本结构是由一系列的单元格(cell)组成的,这些单元格按照一定的排列顺序组成网格布局。每个单元格都可以包含文本、图像等元素,并可以通过设置属性来改变外观和行为。 - **Cell 结构**:每个单元格都...
矩阵排列HTML网页模板采用了灵活的布局策略,如媒体查询(Media Queries)和流式布局(Fluid Grids),确保页面在手机、平板电脑和桌面电脑上都能呈现出最佳的视觉效果。这样的设计使得网站无需针对每个设备单独开发...
- `flex-direction`属性定义主轴方向(行或列),影响元素的排列顺序。 - `justify-content`和`align-items`分别用于沿主轴和交叉轴对齐元素。 - `flex-wrap`控制元素是否换行,可实现单行或多行布局。 - `flex-...
重新排列列 显示/隐藏列 允许数据排序动作 允许分页动作 依存关系 灰烬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”项目中,开发者可能创建了一个自定义的HexagonalGrid类,继承自Kivy的Widget或Layout类,然后重写了布局更新和绘图方法,以在屏幕上绘制出六边形的形状和排列。 **文件名称列表解析** "*...
**Angular Grids:掌握角度数据表与UI-Grid** Angular Grids是一种强大的工具,用于在Angular应用程序中展示和管理大量数据。在这个特定的项目“angular-grids”中,重点是利用Angular框架结合UI-Grid库来创建高效...
这主要依赖于媒体查询(Media Queries)、流式布局(Fluid Grids)和灵活的图片(Flexible Images)这三个关键要素。 在这个jQuery插件中,它会监听浏览器窗口的大小变化,当窗口大小发生变化时,会动态调整图片的...
描述中的“封闭式项目”可能指的是该项目设计时对元素的排列和布局有特定的规则和结构,而“使用网格”则意味着它利用了CSS Grid布局来实现这一点。 **HTML (HyperText Markup Language)** HTML是网页内容的基础,...
Grid容器是包含Grid布局的所有元素,而Grid项目则是容器内的子元素,它们会按照Grid规则进行排列。 **定义Grid轨道** 使用`grid-template-columns`和`grid-template-rows`属性来定义Grid的行和列。这些属性可以接受...
在"frontend-store-learning-grids-curso-main"目录下,我们可以期待找到一系列与创建这种网格布局相关的文件和资源。 首先,HTML5引入了新的 semantic elements(语义元素),如, , , , , , 和,这些元素有助于...
列在行内排列,可以根据屏幕宽度变化进行堆叠或并排显示。系统通常包含多个预定义的断点,这些断点定义了不同屏幕尺寸下的列数和间距。例如,开发者可以设定在大屏幕设备上显示4列,在平板电脑上显示2列,在手机上...
网格设计是一种在平面设计、网页设计和用户界面设计中广泛使用的技术,它是一种将设计元素按照一定的规则排列组合的方法。通过使用网格,设计师可以为各种视觉元素创建一致的结构,使布局更加有组织和易于导航。这种...
响应式设计的核心在于媒体查询(Media Queries)和流式布局(Fluid Grids),但jQuery可以作为辅助工具,用于实现更精细的交互效果。在这个图片画廊中,jQuery可能首先计算出容器的宽度,然后根据这个宽度调整图片的...
1. **选择元素**:使用jQuery的选择器选取需要实现拖动功能的div元素,例如 `$("#grids .grid")` 可以选取所有类名为`grid`的子元素。 2. **绑定事件**:使用`.on()`方法为这些元素绑定鼠标事件,如`mousedown`...