CF1741BFunnyPermutation题解-创新互联
输入一个整数 n n n,要求构造一个长度为 n n n 的排列 p p p, p i ∈ [ 1 , n ] p_i \in [1,n] pi∈[1,n],并同时满足以下两点要求:
创新互联公司执着的坚持网站建设,小程序设计;我们不会转行,已经持续稳定运营十余年。专业的技术,丰富的成功经验和创作思维,提供一站式互联网解决方案,以客户的口碑塑造品牌,携手广大客户,共同发展进步。- 对于排列中的每一个元素,满足在和它相邻的元素中至少有一个元素和它的值相差 1 1 1。
- 下标从 1 1 1 开始,每个下标对应的元素不能和下标相等,形式化的,对于每一个 i ∈ [ 1 , n ] i \in [1,n] i∈[1,n] 都必须满足 p i ≠ i p_i \neq i pi=i。
如果可以构造,输出构造的排列。
如果不可以,输出
−
1
-1
−1。
构造题,首先考虑第一个要求,先想到的就是按顺序排列,但是为了满足各个下标对应元素不能和下标相等,再考虑顺序移动一位,后边的补到前边,但这样就会导致最前边的元素无法满足第一个要求,所以整体向后顺序移动两位,溢出的部分补到前边。
要注意的是,顺序向后移动两位之后还要保证剩下的部分也满足第一个条件,因此这样的操作只适用于 n ≥ 4 n \geq 4 n≥4 的情况,那么对于 n = 1 , 2 , 3 n={1,2,3} n=1,2,3 的情况我们可以特判一下。
因此,下面代码中的 check 函数我只判断了是否满足第二个要求。
形式化的,对于 n ≥ 4 n \geq 4 n≥4的情况,我们在要构造的排列中先放入 n − 1 n-1 n−1 和 n n n,然后依次放入 1 1 1 到 n − 2 n-2 n−2 即可。
代码#includeusing namespace std;
inline long long read()
{long long x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{if (ch == '-')
{f = -1;
}
ch = getchar();
}
while (isdigit(ch))
{x = (x<< 1) + (x<< 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
bool check(vector&v)
{for (ll i = 0; i< v.size(); i++)
{if (v[i] == i + 1)
{return false;
}
}
return true;
}
void solution()
{ll n = 0;
n = read();
if (n == 1)
{cout<< -1<< endl;
return;
}
if (n == 2)
{cout<< 2<< ' '<< 1<< endl;
return;
}
if (n == 3)
{cout<< -1<< endl;
return;
}
vectornums;
nums.push_back(n - 1);
nums.push_back(n);
for (ll i = 1; i<= n - 2; ++i)
{nums.push_back(i);
}
if (check(nums))
{for (ll i = 0; i< nums.size(); i++)
{cout<< nums[i]<< " ";
}
cout<< endl;
}
else
{cout<< -1<< endl;
}
}
int main()
{ll T = 0;
T = read();
for (ll i = 0; i< T; i++)
{solution();
}
return 0;
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网站题目:CF1741BFunnyPermutation题解-创新互联
当前链接:http://scyanting.com/article/dgphgh.html