本文主要是介绍1620 - Lazy Susan【数学】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
- 题目大意
- 样例
- input
- output
- 解释
- 思路
- 代码
- Hit
题目大意
传送门
将1~n(8<=n<=500)放到一个圆盘里,每个数字都出现一次。(可以首尾相连)
每次可以选择连续的4个数字翻转顺序,最后问能不能变成1,2,3,4,5,6…n的顺序。
样例
input
2
9
1 9 8 3 7 6 5 4 2
11
1 3 2 4 5 6 7 8 9 10 11
output
possible
impossible
解释
对于第一组样例:
对于第二组样例不能凑成1~n的排列。
思路
看到这个题目我有两种思路。
一种思路是搜索来求得最后的结果,先把n放在第n个位置,然后将n-1放在第n-1个位置,依次递推。
另一种思路是逆序数,一个序列中的当前数字比后面的数字大,被称为一个逆序。序列中逆序的总数就是逆序数。
比如:
序列: 1 2 3 4 逆序数为 0+0+0+0 = 0
序列: 4 3 2 1 逆序数为 3+2+1+0 = 6
序列: 1 3 2 4 逆序数为 0+1+0+0 = 1
序列: 4 2 3 1 逆序数为 3+1+1+0 = 5
每次将四个数字翻转顺序的操作来说:
xxxx 1 3 2 4 xxxx 逆序数为X+1=N
xxxx 4 2 3 1 xxxx 逆序数为X+6-1=N+4
xxxx 1 4 2 3 xxxx 逆序数为X+2=N
xxxx 3 2 4 1 xxxx 逆序数为X+6-2=N+2
每次翻转逆序数增加或者减少都是偶数。
若逆序数为奇数并且序列的长度为奇数,则结果为impossible。
比如
1 2 3 4 6 5 :逆序数为1
4 3 2 1 6 5 :逆序数为7
5 4 3 2 1 6 :逆序数为10
6 5 4 3 2 1:逆序数为15
代码
#include<cstdio>
#include<map>
#include<queue>
#include<cstring>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include <math.h>
#include <stack>
using namespace std;
const int maxn = 505;int a[maxn];int main()
{int CaseNum;scanf("%d",&CaseNum);while(CaseNum--){int n;scanf("%d",&n);for(int i=0;i<n;i++) scanf("%d",&a[i]);int ans = 0;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(a[i]>a[j]) ans++;}}//printf("ans : %d\n",ans);if(ans&1 && n&1) printf("impossible\n");else printf("possible\n");}}
/*
input
2
9
1 9 8 3 7 6 5 4 2
11
1 3 2 4 5 6 7 8 9 10 11output
possible
impossible
*/
Hit
这篇关于1620 - Lazy Susan【数学】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!