黑马程序员技术交流社区

标题: 每天一题坚持一个月....之五 [打印本页]

作者: 刘胜寒    时间: 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
  1. class Main
  2. {
  3.         public static void main(String[] args)
  4.         {
  5.                     Scanner cin = new Scanner(System.in);
  6.                     while(cin.hasNext())
  7.                     {
  8.                             int n = cin.nextInt();
  9.                             int[] ans, tmp;
  10.                             int  Max=0, i=0, p=0, tot=0, j=0;
  11.                             ans = new int[n+1];
  12.                             tmp = new int[n+1];
  13.                             for(i=1;i<=n;i++)// 这个地方的用法很有趣 有兴趣可以把 tmp 打印出来
  14.                             {
  15.                                     ans[i]=cin.nextInt();
  16.                                     tmp[ans[i]]=i;
  17.                             }
  18.                             Max=0; i=1; p=1; tot=1;
  19.                             int temp;
  20.                             while(i<n)// 利用逆序数  
  21.                             {
  22.                                     temp = ans[p]+1;
  23.                                     if(temp>n) temp = 1;
  24.                                     j =  tmp[temp];
  25.                                     if(j>p)tot++;
  26.                                     else tot=1;
  27.                                     Max = Math.max(Max, tot);
  28.                                     p=j;
  29.                                    
  30.                                     i++;
  31.                             }
  32.                             System.out.println(n-Max);
  33.                     }
  34.         }
  35. }
复制代码





欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2