黑马程序员技术交流社区
标题:
每天一题坚持一个月....之五
[打印本页]
作者:
刘胜寒
时间:
2013-4-12 10:55
标题:
每天一题坚持一个月....之五
本帖最后由 刘胜寒 于 2013-4-13 12:27 编辑
描述
定义一种循环有序序列，该序列可看做首尾相连的圈状序列，从某个位置开始向后数至该位置的前一位，数过的元素都是从小到大排序的。例如对于1,2,3,4这四个数，符合条件的循环有序序列有1,2,3,4；2,3,4,1；3,4,1,2；4,1,2,3四个。
定义一种操作，可以在序列里任选一个位置的数，把它移动到序列的第一个位置，例如序列1,2,3,4，对3进行操作后序列变为3,1,2,4。
现在输入一个长度为n的初始序列，问至少经过多少次操作可以使原序列变成一个循环有序序列。
输入
输入文件只有一组数据。第一行一个整数N(1<=N<=30000)。第二行N个整数Ai（1<=Ai<=N），满足对于任意的i!=j,保证Ai!=Aj，即1~N的一个排序。
输出
输出文件只有一行，包含一个整数，表示至少需要的操作次数。
样例输入
4
3 2 4 1
样例输出
1
提示
对于3,2,4,1存在四种循环有序序列，需要的操作次数分别为：
1,2,3,4 2次
2,3,4,1 1次
3,4,1,2 3次
4,1,2,3 3次
所以最少的操作次数为1次。
输入输出说明
对于20%的数据，N<=20。
对于40%的数据，N<=500。
对于70%的数据，N<=5000。
对于100%的数据，N<=30000。
题目来源
2007年全国青少年信息学竞赛广东队组队选拔赛
友情链接:
每天一题坚持一个月....之四
http://bbs.itheima.com/thread-45153-1-1.html
每天一题坚持一月....之三
http://bbs.itheima.com/thread-44986-1-1.html
每天一题坚持一个月....之二
http://bbs.itheima.com/thread-44819-1-1.html
每天一题坚持一个月....之一
http://bbs.itheima.com/thread-44753-1-1.html
作者:
邵震
时间:
2013-4-12 11:01
抢钱抢粮抢清新
作者:
张旺达
时间:
2013-4-12 11:07
寒哥 求答案~！
作者:
易杰
时间:
2013-4-12 11:45
强大。。。。。。。。。
作者:
刘胜寒
时间:
2013-4-13 12:27
class Main
{
public static void main(String[] args)
{
Scanner cin = new Scanner(System.in);
while(cin.hasNext())
{
int n = cin.nextInt();
int[] ans, tmp;
int Max=0, i=0, p=0, tot=0, j=0;
ans = new int[n+1];
tmp = new int[n+1];
for(i=1;i<=n;i++)// 这个地方的用法很有趣 有兴趣可以把 tmp 打印出来
{
ans[i]=cin.nextInt();
tmp[ans[i]]=i;
}
Max=0; i=1; p=1; tot=1;
int temp;
while(i<n)// 利用逆序数
{
temp = ans[p]+1;
if(temp>n) temp = 1;
j = tmp[temp];
if(j>p)tot++;
else tot=1;
Max = Math.max(Max, tot);
p=j;
i++;
}
System.out.println(n-Max);
}
}
}
复制代码
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2