rockethon2015 B題 Permutations 規律+構造
題意:求使所給公式值最大的第m個排列。
思路:假設已知使f(p)最大的n-1的排列,那麼對於使f(p)最大的n的排列,把n放在(n-1)兩邊均可。因為n放在(n-1)兩邊,增值為
1+2+...+n,而如果不放在兩邊,(n-1)到n之間的值n擺放位置,對於i,如果m<2^(n-i-1),
那麼i擺在pos,不然放到可放到的最後面,即last位置。因為接下來(i+1)一定在i左邊,而之後比(i+1)大也一定在i左邊。詳見代碼:
/*********************************************************
file name: B.cpp
author : kereo
create time: 2015年02月08日 星期日 21時45分31秒
*********************************************************/
#include
#include
#include
#include
#include
#include