思维题 循环数组

思维题.

题意

输入一个n，输入n个数
可以进行两个操作
第一个操作： 把倒数第二个数放到第一个
第二个操作：把第一个数放到最后一个
注意连续进行同一个操作算操作一次
问把原序列变成1到n的序列最少进行多少次第一个操作

分析

首先把序列看成一个环，指针指向最后一个数，第一个操作相当于把除了指针所指的数旋转，第二个操作相当于把整个序列旋转，指针指向的数会改变

样例1 如果所示，我们可以发现，先找到最长上升子序列，操作1的数量就等于数列长度–最长上升子序列。

#include <bits/stdc++.h>
#define ll long long
#define T int t;scanf("%d", &t);while(t--)
using namespace std;
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
const ll mod = 1e9+7;
const int maxn = 2e5+5;
int a[maxn];
int dp[maxn];
int main(){
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
scanf("%d", a + i);
int maxx = 0;
//dp[j]表示以第i个数为结尾的最长上升子序列
for(int i = 1; i <= n; i ++){
//以每个数为头
for(int j = 1; j <= n; j ++){	//求最长上升子序列
dp[j] = 1;
for(int k = 1; k < j; k ++){
if(a[k] < a[j])
dp[j] = max(dp[j], dp[k] + 1);
maxx = max(maxx, dp[j]);
}
}
int t = a[1];
//移动数列
for(int j = 1; j < n; j ++) a[j] = a[j + 1];
a[n] = t;
}
printf("%dn", n - maxx);
return 0;
}

最后

以上就是光亮鞋垫为你收集整理的思维题 循环数组的全部内容，希望文章能够帮你解决思维题 循环数组所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。