翼支付编程大赛――修改数列

2014-12-18 为码而活 PHP教程 关注382次 已收录
当前位置：波比源码 > 翼支付编程大赛――修改数列
正文概述

题目详情（修改数列）：

我们有1个数列。我们可以把其中的任意1些项替换成其他的正整数，但是我们不能删掉项，也不能交换项的顺序。请问最少需要几次替换，才能把数列变成严格单调递增的？

输入格式

多组数据，每组数据第1行1个正整数n (n<=1000000)

每组数据第2行是n个空格分隔的非负整数,每一个不超过10^9，表示数列中的数。

输出格式

对每组数据，输出1行，包括其最少的替换次数。


答题说明:

输入样例  

3

4 10 20

5

1 7 2 20 22

输出样例

0

1

先说下思想：鉴戒最长递增子序列（LIS）的思想，添加限制条件：元素值>=元素下标；元素之间的差值>=元素下标之间的差值。
举例：A[0…8] = {2, 1, 5, 3, 6, 4, 8, 9, 7}
设置两个数组：B记录最长递增子串（符合本题题意的条件下的），Pos记录子串中各元素在原数组中的下标。设置变量：len记录子串长度。
（1）从后往前找数组A，第1个满足：元素值>=下标的元素。应当为9，所以有B[0]=9, Pos[0]=7,len=1；
（2）再看9之前的元素8，先判断它是不是>=下标，可知成立。再判断(B[len⑴]-A[6] = 9⑻) >= (1=Pos[len⑴]⑹)，成立，因此子串中加入元素8。那末B[0,1] = {9,8}， Pos[0,1] = {7,6}, len=2；
（3）再看8之前的元素4，由于它<下标，因此直接跳过；
（4）再看4之前的元素6，它>=下标，(B[len⑴]-A[4] = 8⑹) >= (2 = Pos[len⑴] – 4)，因此子串加入元素6，那末B[0,1,2] = {9,8,6}，Pos[0,1,2]={7,6,4}, len = 3;
（5）再看6之前的元素3，>=下标，6⑶>=1，那末B[0,1,2,3]={9,8,6,3}，Pos[0,1,2,3]={7,6,4,3},len=4；
（6）再看3之前的5，>=下标，不符合3⑸>=1，由于5>3，得看是不是要取代B中已有的元素。在B中从后往前找到，恰好大于5的数，那就是6。接下来就要判断是不是应当让5来取代6后面的元素3的位置。由于6⑸=1>=(2=Pos[2]⑵)不成立，因此不能让5来替换，所以还是跳过；
（7）再看5之前的1，均符合要求，因而B[0,1,2,3,4]={9,8,6,3,1}，Pos[0,1,2,3,4]={7,6,4,3,1},len=5；
（8）再看1之前的2，>=下标，不符合1⑵>=1，由于2>1，得看是不是要取代B中已有元素。一样找到3，由于3⑵>=3不成立，所以跳过。
至此，得到符合要求的最长不需要改动的子串，那末元数组总长度―len就是最少需要替换的个数。
要求用java，基本输入输出也不会，只得求助百度了，下面是小菜鸡的代码：
<pre name="code" class="java">import java.util.Scanner;  
  
public class Main {    
    public static void main(String[] args) {  
        Scanner in = new Scanner(System.in);  
        int n;  
        int[] num;  
        while(in.hasNext()){  
            n = in.nextInt();
            num = new int[n];
            for(int i = 0; i < n; i++)
            	num[i] = in.nextInt();
            int len = 0;
            for(int i = n; i > 0; i--){//暴力破解！！
            	int tmp = lis(num, i);
            	len = tmp > len ? tmp : len;
            }
            System.out.println(n-len);
        }
    }  
  
    private static int lis(int[] num, int n) {
		// TODO Auto-generated method stub
		int[] bnum = new int[n];
		int[] bpos = new int[n];
		int init;	//从后到前，第1个元素值大于等于下标（从0开始）的元素为首
		int len;	//最长严格单音调串长度
		for(init = n - 1; init >= 0; init--){
			if(num[init] >= init){
				bnum[0] = num[init];
				bpos[0] = init;
				break;
			}
		}
		len = 1;
		if(init < 0){
			return 1;
		}
		for(int i = init - 1; i >= 0; i--){
			if(num[i] >= i){	//值大于等于下标才有比较的意义
				if(bnum[len - 1] - num[i] >= bpos[len - 1] - i){    
				//值的差大于等于下标的差才可以添加
					bnum[len] = num[i];
					bpos[len++] = i;
				}else if(num[i] > bnum[len - 1]){
					int pos = find(bnum, bpos, len, num[i], i);	
					//寻觅替换位置
					if(pos != ⑴){
						bnum[pos] = num[i];
						bpos[pos] = i;
					}
				}
			}
		}
		return len;
	}

	private static int find(int[] bnum, int[] bpos, int len, int number, int pos) {
		// TODO Auto-generated method stub
		int i = 0;
		for(i = len - 1; i > 0; i--){	//找到恰好比number大的元素位置
			if(bnum[i - 1] > number){
				break;
			}
		}
		if(i <= 0)
			return 0;
		else{
			if(bnum[i - 1] - number >= bpos[i - 1] - pos)	//判断替换可行否
				return i;
			else
				return ⑴;
		}
	}
}



      

      

          

          
          
      


波比源码 – 精品源码模版分享 | www.bobi11.com 

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！

2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！

3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！

4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！

5. 如有链接无法下载、失效或广告，请联系管理员处理！

6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！

7. 本站源码并不保证全部能正常使用，仅供有技术基础的人学习研究，请谨慎下载

8. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！


波比源码 » 翼支付编程大赛――修改数列








  
  
  


      分享到：

      
      

      

      
  


  
 


    

  





  

    
    
  


      
      

        
相关推荐

        

                     

              
            

                      

              
            

                      

              
            

                      

              
            

                  

      

    
  






    


        
            


                79 评论
            




            
    

                


  
  1. 

     
    2. 



  
  2. 

     
    3. 



  
  3. 

     
    4. 



  
  4. 

     
    5. 



  
  5. 

    
    

      
    

        
      
    



      
    

        



        
    

          



          
        
    



        
    

          
    purchase fildena generic order robaxin buy robaxin 500mg generic
    

        
    



        
      
    

    
     
    6. 



  
  6. 

     
    7. 



  
  7. 

     
    8. 



  
  8. 

     
    9. 



  
  9. 

     
    10. 



  
  10. 

     
    11. 



  
  11. 

     
    12. 



  
  12. 

     
    13. 



  
  13. 

    
    

      
    

        
      
    



      
    

        



        
    

          



          
        
    



        
    

          
    pharmacie en ligne tadalafil 20mg cialis 5mg prix sildenafil 200mg comprimГ©
    

        
    



        
      
    

    
     
    14. 



  
  14. 

     
    15. 



  
  15. 

    
    

      
    

        
      
    



      
    

        



        
    

          



          
        
    



        
    

          
    tadalafil 10mg bestellen viagra ohne rezept sildenafil 100mg kaufen ohne rezept
    

        
    



        
      
    

    
     
    16. 



  
  16. 

    
    

      
    

        
      
    



      
    

        



        
    

          



          
        
    



        
    

          
    isotretinoin 20mg oral stromectol pills ivermectin 6 mg without prescription
    

        
    



        
      
    

    
     
    17. 



  
  17. 

    
    

      
    

        
      
    



      
    

        



        
    

          



          
        
    



        
    

          
    buy altace 10mg cost temovate purchase astelin generic
    

        
    



        
      
    

    
     
    18. 



  
  18. 

     
    19. 



  
  19. 

     
    20. 



  
  20. 

     
    21. 



  
  21. 

     
    22. 



  
  22. 

     
    23. 



  
  23. 

    
    

      
    

        
      
    



      
    

        



        
    

          



          
        
    



        
    

          
    molnupiravir 200 mg oral naprosyn uk purchase prevacid generic
    

        
    



        
      
    

    
     
    24. 



  
  24. 

     
    25. 



  
  25. 

     
    26. 



  
  26. 

     
    27. 



  
  27. 

    
    

      
    

        
      
    



      
    

        



        
    

          



          
        
    



        
    

          
    medroxyprogesterone 5mg over the counter buy provera 5mg order periactin 4 mg for sale
    

        
    



        
      
    

    
     
    28. 



  
  28. 

     
    29. 



  
  29. 

     
    30. 



  
  30. 

     
    31. 



  
  31. 

     
    32. 



  
  32. 

    
    

      
    

        
      
    



      
    

        



        
    

          



          
        
    



        
    

          
    buy azithromycin 250mg online cheap order zithromax 250mg buy gabapentin 100mg without prescription
    

        
    



        
      
    

    
     
    33. 



  
  33. 

     
    34. 



  
  34. 

     
    35. 



  
  35. 

     
    36. 



  
  36. 

     
    37. 



  
  37. 

     
    38. 



  
  38. 

    
    

      
    

        
      
    



      
    

        



        
    

          



          
        
    



        
    

          
    omeprazole brand slots games online blackjack free
    

        
    



        
      
    

    
     
    39. 



  
  39. 

     
    40. 



  
  40. 

     
    41. 



  
  41. 

     
    42. 



  
  42. 

     
    43. 



  
  43. 

     
    44. 



  
  44. 

    
    

      
    

        
      
    



      
    

        



        
    

          



          
        
    



        
    

          
    tadalafil liquid brand viagra sildenafil us
    

        
    



        
      
    

    
     
    45. 



  
  45. 

     
    46. 



  
  46. 

     
    47. 



  
  47. 

     
    48. 



  
  48. 

     
    49. 



  
  49. 

     
    50. 



  
  50. 

     
    51. 



  
  51. 

    
    

      
    

        
      
    



      
    

        



        
    

          



          
        
    



        
    

          
    order keflex 500mg keflex 125mg ca purchase erythromycin generic
    

        
    



        
      
    

    
     
    52. 



  
  52. 

     
    53. 



  
  53. 

    
    

      
    

        
      
    



      
    

        



        
    

          



          
        
    



        
    

          
    buy ceftin 250mg without prescription buy cefuroxime brand methocarbamol 500mg
    

        
    



        
      
    

    
     
    54. 



  
  54. 

    
    

      
    

        
      
    



      
    

        



        
    

          



          
        
    



        
    

          
    blackjack online money casino gambling cialis tadalafil 5mg
    

        
    



        
      
    

    
     
    55. 



  
  55. 

     
    56. 



  
  56. 

     
    57. 



  
  57. 

     
    58. 



  
  58. 

    
    

      
    

        
      
    



      
    

        



        
    

          



          
        
    



        
    

          
    buy sildenafil 50mg sale budesonide us brand budesonide
    

        
    



        
      
    

    
     
    59. 



  
  59. 

     
    60. 



  
  60. 

    
    

      
    

        
      
    



      
    

        



        
    

          



          
        
    



        
    

          
    cost retin avanafil us order avana 100mg sale
    

        
    



        
      
    

    
     
    61. 



  
  61. 

     
    62. 



  
  62. 

     
    63. 



  
  63. 

     
    64. 



  
  64. 

     
    65. 



  
  65. 

     
    66. 



  
  66. 

    
    

      
    

        
      
    



      
    

        



        
    

          



          
        
    



        
    

          
    order singulair viagra uk viagra sildenafil 200mg
    

        
    



        
      
    

    
     
    67. 



  
  67. 

     
    68. 



  
  68. 

     
    69. 



  
  69. 

     
    70. 



  
  70. 

     
    71. 



  
  71. 

    
    

      
    

        
      
    



      
    

        



        
    

          



          
        
    



        
    

          
    doxycycline usa cleocin cost order cleocin 150mg pills
    

        
    



        
      
    

    
     
    72. 



  
  72. 

     
    73. 



  
  73. 

     
    74. 



  
  74. 

     
    75. 



  
  75. 

     
    76. 



  
  76. 

    
    

      
    

        
      
    



      
    

        



        
    

          



          
        
    



        
    

          
    order requip 2mg online cheap ropinirole drug purchase labetalol online cheap
    

        
    



        
      
    

    
     
    77. 



  
  77. 

     
    78. 



  
  78. 

     
    79. 



  
  79. 

     
    80. 

            




            


        


        


        


        	

		
发表评论 






 


 


	

	
    














    
Hi, 如果你对这款模板有疑问，可以跟我联系哦！


    联系站长










				


			


		


		
			


				

			


		
	











 



	
    

    

	


	

	

	







    

    


	    


	        

	        

	    


    














  








	










    







  

  

      
      
    
    

  
  












 














 

	


	


	















    	


         
        赞助VIP

        
         享更多特权，建议使用 QQ 登录


        
 

            

        




        

        
 QQ登录


        

    	













    

    
喜欢我嘛？喜欢就按“ctrl+D”收藏我吧！♡