首页 > 代码库 > CF 275(div.1) A Diverse Permutation
CF 275(div.1) A Diverse Permutation
Diverse Permutation
题意：一个1~n的无重复整数序列，要求打印其中一种排列，使新序列相邻两项之差的绝对值去重后的个数刚好为k个
(1 <= k < n <= 10^5)
输入：n,k
输出：新序列
思路：想了一下，先考虑k最大和k最小取值时的序列排列情况
1) k最大时：k = n-1 序列：1,n,2,n-1,3,n-2.... 相邻两项绝对值差：n-1,n-2,n-3...1
2) k最小时：k = 1 序列：1,2,3...n | n,n-1,n-2...1
k取值为 [1,n-1] 那么中间的取值就这两个情况进行组合，前段用1)，剩下数用2)
当k为奇数时，2)用升序；当k为偶数时，2)用降序
好，撸代码
1 package golao.org.cf275; 2 3 import java.io.BufferedReader; 4 import java.io.IOException; 5 import java.io.InputStreamReader; 6 import java.util.Arrays; 7 import java.util.StringTokenizer; 8 9 public class DiversePermutation {10 11 public static void main(String[] args) throws IOException {12 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));13 StringTokenizer stk = new StringTokenizer(br.readLine());14 int n,k;15 n = Integer.parseInt(stk.nextToken()); 16 k = Integer.parseInt(stk.nextToken());17 System.out.println(print(findPermutation(n,k)));18 19 }20 public static int[] findPermutation(int n,int k)21 {22 int[] ary = new int[n];23 for(int i=1;i<=n;i++){24 ary[i-1] = i;25 }26 int[] aryResult = new int[n];27 int count = n-1;28 //前段29 for(int j=1,i=0;j<=k;j+=2,i++){30 aryResult[j-1] = ary[i];31 aryResult[j] = ary[count--];32 }33 //后段34 if(k%2==0){35 for(int index=k;index<n;index++){36 aryResult[index] = ary[count--];37 }38 }else{39 for(int index=k;index<n;index++){40 aryResult[index] = aryResult[index-1]+1;41 }42 }43 return aryResult;44 }45 public static String print(int[] ary){46 StringBuffer sb = new StringBuffer("");47 for(int i=0;i<ary.length;i++){48 sb.append(ary[i]);49 sb.append(" ");50 }51 return sb.toString();52 }53 54 }
提交给CF，运行通过，77ms
CF 275(div.1) A Diverse Permutation
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。