C. Diverse Permutation(Codeforces Round #275(div2)
1 second
256 megabytes
standard input
standard output
Permutation p is an ordered set of integers p1, p2, ..., pn,
consisting of n distinct positive integers not larger than n.
We'll denote as nthe length of permutation p1, p2, ..., pn.
Your task is to find such permutation p of length n,
that the group of numbers |p1 - p2|, |p2 - p3|, ..., |pn - 1 - pn| has
exactly k distinct elements.
The single line of the input contains two space-separated positive integers n, k (1 ≤ k < n ≤ 105).
Print n integers forming the permutation. If there are multiple answers, print any of them.
3 2
1 3 2
3 1
1 2 3
5 2
1 3 2 4 5
By |x| we denote the absolute value of number x.
用n个数1~n,每一个数仅仅能用一次。组成差值的绝对值有k个数。为1~k。
输出任一个方案。
构造题,我是这样构造的,取前k+1个数。第一个数取1,先+k。后一个数-(k-1),在后一个数+k-2.......这样从两头往
中间靠拢。既取完了k+1个数。又构造了1~k的差值绝对值,至于k+1后的嘛,每次+1即可了。
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=100000+1000;
int ans[maxn];
int main()
{
int n,k;
ans[1]=1;
scanf("%d%d",&n,&k);
if(k==1)
{
for(int i=1;i<=n;i++)
ans[i]=i;
}
else
{
for(int i=2;i<=k+1;i++)
{
if(i%2)
ans[i]=ans[i-1]-(k-i+2);
else
ans[i]=ans[i-1]+(k-i+2);
}
int cur=1;
for(int i=k+2;i<=n;i++)
{
ans[i]=k+1+cur;
cur++;
}
}
for(int i=1;i<n;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[n]);
return 0;
}
最新文章
- ajax传输中文乱码解决方法
- MySQL:索引工作原理
- jquery练习
- 安装 phpredis 扩展
- Hadoop、Zookeeper、Hbase分布式安装教程
- TCP三次握手及四次挥手详细图解
- Scala 具体的并行集合库【翻译】
- C/C++代码中的笔误
- linux find 命令详解
- Android PopupWindows使用
- (转)Sencha Touch和jQuery Mobile的比较
- comparison of floating point numbers with equality operator. possible loss of precision while rounding values
- 【转】Android 最火框架XUtils之注解机制详解
- 跨平台的CStdString类,实现了CString的接口
- java 异常处理机制及说明。
- Spring 5:以函数式方式注册 Bean
- Hawk原理:通过IEnumerable实现通用的ETL管道
- SQL Server 自动循环归档分区数据脚本
- 多重背包--java
- 国服最强JWT生成Token做登录校验讲解,看完保证你学会!
热门文章
- 爬虫来啦!Day91
- LOJ #10121 与众不同 (RMQ+二分)
- 在WIN7、WIN10操作系统用WebDAV映射网络驱动器需要的操作
- Adobe Flex迷你教程 —Flex圆角容器
- Linux文件属性(属主属组权限)
- 【BZOJ 1296】 [SCOI2009]粉刷匠
- [terry笔记]11gR2_DataGuard搭建_拷贝数据文件
- LaTeX 写算法伪码
- Mock+Proxy在SDK项目的自己主动化測试实战
- 最强最全干货分享:Android开发书籍、教程、工具等