首页 > 代码库 > Codeforces 482 - Diverse Permutation 构造题
Codeforces 482 - Diverse Permutation 构造题
这是一道蛮基础的构造题。
- k +(k - 1) -(k - 2)
1 + k , 1 , k , 2, ...................
\ / \ / \ /
k k-1 k-2
如图所示,先构造第一个数,就是1 + k, 然后接下来每个数字和上个数相差k , k -1 , k -2
这样下来,最后一个数字就是一个中间的数字,过程就是不断向中间逼近。
在k + 1后面的数字,只要升序输出就可以了。
构造题还是不太熟练阿 QAQ
贴代码了:
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler#include <stdio.h>#include <iostream>#include <cstring>#include <cmath>#include <stack>#include <queue>#include <vector>#include <algorithm>#define ll long long#define Max(a,b) (((a) > (b)) ? (a) : (b))#define Min(a,b) (((a) < (b)) ? (a) : (b))#define Abs(x) (((x) > 0) ? (x) : (-(x)))using namespace std;const int INF = 0x3f3f3f3f;int a[100001];int main(){ int i, j, k, t, m, n; while(EOF != scanf("%d%d",&n,&k)){ if(k == 1){ for(i = 1; i < n; ++i) printf("%d ",i); printf("%d\n",n); continue; } a[1] = 1 + k; for(i = 2; i <= k + 1; ++i){ if(i % 2 == 0) a[i] = a[i - 1] - (k - (i - 2)); else a[i] = a[i - 1] + (k - (i - 2)); } int cur = 1; for(i = k + 2; i <= n; ++i){ a[i] = k + 1 + cur++; } for(i = 1; i < n; ++i){ printf("%d ",a[i]); } printf("%d\n",a[n]); } return 0;}
Codeforces 482 - Diverse Permutation 构造题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。